[報告]HDU 4413 Logical Expression

Abstract
HDU 4413 Logical Expression
むやみにカノ図を作る
 
Body
ソurce
http://acm.hdu.edu.cn/showproblem.php?pid=4413

Description
N変数のすべての2^Nの一番小さい項目を指定して、すべての一番小さい項目に合致する一番美しい(一番短い場合、辞書の順序が一番小さい)のと式を求めます.
Solution
天王はまだ自信過剰です.えっと、…
考え方は実はとても簡単です.
カノグラフを復習しましょう.カノグラフの上にいくつかの円を囲むことを考慮してください.これらの円は上書きされていて、すべての1の一番小さい項目だけをカバーしています.表現はこれらの丸の項目です.
カノグラフ上のいずれか1を考えると、この1をカバーする全ての非極大圏は最終的な答えの項ではないということができます.反対に、この1をカバーする極大圏が最終的な答えの項であると仮定します.丸が大きくないため、それは必ずある極大圏に属しています.明らかに極大圏化の簡単な項の長さは極大圏より小さいです.
そこで可能なすべての最終的な答えの項目は、カノグラフの大きな丸です.天王の誤りは彼が1つの最大の円(すべての極大圏の中で最も美しい)をカバーすることを求めるだけで、これは貪欲に相当して、間違いです.このところは簡単には分かりません.私もデータを試してみてやっと分かりました.
ですから、私たちはそれぞれの1つに対して、その大きな輪をカバーして、大きな輪の集合を得ます.(uniqueに注意してください.)各極大圏の表現長が一定であることに注意して、まず極大圏ごとに最適表現を求めます.これらの極大圏を使って最適なカバーを求めます.これはいい方法がないようです.検索するしかないです.大きなサークルの集合をソートすると検索速度が速くなります.
コード
コードは天王のwaのコードに基づいて変更されましたので、見苦しいです.

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#include<string>

using namespace std;



typedef pair<string, int> node;

vector<node> ans;

bool vis[50];

int V[50];



bool cmp(string s1,string s2){

    return s1+s2<s2+s1;

}

bool cmp2(string s1,string s2){

    return s1+"+"+s2<s2+"+"+s1;

}

bool hmr(node a, node b) {

    if (a.second==b.second) {

        if (a.first.length()==b.first.length()) return a.first<b.first;

        return a.first.length()<b.first.length();

    }

    return a.second<b.second;

}



bool operator==(node a, node b) {

    return a.first==b.first && a.second==b.second;

}



string StInS(int s,int n,int ors){

    int i;

    vector<string> tmpAns;

    for (i=0;i<(1<<n);i++){

        if ((i&s)==(ors&s))

            if (V[i]==0) return "";

    }

    if (s==0) return "1";

    string tmp;

    for (i=0;i<n;i++) if (s&(1<<i)){

        tmp="";

        if (!(ors&(1<<i)))

            tmp+='-';

        tmp+=(char)(i+'A');

        tmpAns.push_back(tmp);

    }

    sort(tmpAns.begin(),tmpAns.end(),cmp);

    tmp="";

    for (i=0;i<tmpAns.size();i++)

        tmp+=tmpAns[i];

    return tmp;

}



void getans(int s, int n) {

    int i,j;

    int minsize = 0x3fff;

    vector<node> tmp;

    for (i=0;i<(1<<n);i++) {

        int ctrl=__builtin_popcount(i);

        if (ctrl>minsize) continue;

        string tans2=StInS(i,n,s);

        if (tans2.empty()) continue;

        if (ctrl<minsize) {

            minsize = ctrl;

            tmp.clear();

        }

        int res = 0;

        for (j = 0; j < 1<<n; ++j)

            if ((j&i)==(s&i)) res |= 1<<j;

        tmp.push_back(make_pair(tans2, res));

    }

    for (i = 0; i < tmp.size(); ++i)

        ans.push_back(tmp[i]);

}



int N, M;

int all;

int best;

bool use[64], ause[64];



void dfs(int i, int len, int cover) {

    if (len >= best) return;

    if (cover==all) {

        memcpy(ause, use, sizeof(use));

        best = len;

        return;

    }

    if (i==M) return;

    use[i] = 1;

    dfs(i+1, len+ans[i].first.length()+1, cover|ans[i].second);

    use[i] = 0;

    dfs(i+1, len, cover);

}



int main(){

    int i,s,j,v;

    int cas=0;

    for (;;){

        scanf("%d",&N);

        if (N==0) break;

        for (i=0;i<(1<<N);i++){

            s=0;

            vis[i] = 0;

            for (j=0;j<N;j++){

                scanf("%d",&v);

                s^=(v<<j);

            }

            scanf("%d",&V[s]);

        }

        ans.clear();

        memset(vis, 0, sizeof vis);

        all = 0;

        for (s = 0; s < 1<<N; ++s)

            if (V[s]){

                all |= 1<<s;

                getans(s, N);

            }

        if (ans.size()==0) {

            puts("-AA");

            continue;

        }

        if (ans[0].first[0]=='1') {

            puts("-A+A");

            continue;

        }

        sort(ans.begin(), ans.end(), hmr);

        M = unique(ans.begin(), ans.end())-ans.begin();

        sort(ans.begin(), ans.begin()+M);

        best = 0x3fffffff;

        memset(use, 0, sizeof use);

        memset(ause, 0, sizeof ause);

        dfs(0, 0, 0);

        vector<string> astr;

        for (i = 0; i < M; ++i)

            if (ause[i]) astr.push_back(ans[i].first);

        sort(astr.begin(), astr.end(), cmp2);

        string fin = astr[0];

        for (i = 1; i < astr.size(); ++i)

            fin += "+"+astr[i];

        cout << fin << '
';

    }

    return 0;

}