首页 > 搜索 > DFS搜索 > HDU 4413-Logical Expression-图-[解题报告]HOJ
2015
07-16

HDU 4413-Logical Expression-图-[解题报告]HOJ

Logical Expression

问题描述 :

Happy birthday to you!

Your professor gives you a strange device as your birthday gift. But your experience tells you, it is a trap.

Just as expected, he smirks, and then says slowly: "This device is my new invention. Only you, my most brilliant student, deserve to have it."

"Thanks, I will keep it up." You reply.

"However," silent for a while, he starts again: "unfortunately, I have lost its original circuit diagram. So I need you to do some researches on it and use a simple logical expression to describe its characteristics. You won’t let me down, will you?"

He laughs, pats you on the back, then turns and stalks off, leaves you, the poor guy, with the "gift" on your hands.

You collect yourself, and start looking at the "lovely" thing. It is a black box, with n inputs labeled from the first capital letter (A) to the n-th capital letter, as well as one unique output. All the inputs and the output are one-bit binary numbers (either 0 or 1).

Then you sit down, put the device on the desk, take out the tools, examine all possible combinations of input values and record the output on the paper.

After everything gets ready, now it is just a piece of cake for you to give a correct logical expression for it.

A correct logical expression should be:
1. A not null string only contains ‘+’, ‘-’ and capital letters from the first (A) to the n-th;
2. A single capital letter in range is a legal logical expression, and its output equals to the value of the input labeled by this letter;
3. If E is a legal logical expression, then NOT operation -E is a legal logical expression;
4. If E and F are legal logical expressions, then AND operation EF is a legal logical expression;
5. If E and F are legal logical expressions, then OR operation E+F is a legal logical expression;
6. In a legal logical expression, you should first do NOT operations from the left to the right, then AND operations from the left to the right, and finally the OR operations from the left to the right;
7. A logical expression is correct if and only if with any possible combinations of input values, its output is the same as which the device outputs.

But as a down-to-earth idealist, you are never satisfied with this. You want to give the most beautiful logical expression like this:
1. It is a correct logical expression;
2. It is the shortest one (not null) among all correct logical expressions;
3. If there are still many available logical expressions, choose the lexicographically least one.

输入:

There are several test cases in the input.

Each test case begins with one integer n (1 <= n <= 5), indicating the number of inputs of the device.
Then 2n lines follow. Each line contains (n + 1) one-bit binary numbers, separated by spaces. The first n numbers indicate the value of the n inputs in order, and the last one is the corresponding output.
The 2n sets of inputs are different with each other.
The input ends with n = 0.

输出:

There are several test cases in the input.

Each test case begins with one integer n (1 <= n <= 5), indicating the number of inputs of the device.
Then 2n lines follow. Each line contains (n + 1) one-bit binary numbers, separated by spaces. The first n numbers indicate the value of the n inputs in order, and the last one is the corresponding output.
The 2n sets of inputs are different with each other.
The input ends with n = 0.

样例输入:

3
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
0

样例输出:

-A-CB+-BC+AC
Hint
In ASCII table, '+' < '-' < 'A' < 'B' < 'C' < 'D' < 'E'.

Abstract

HDU 4413 Logical Expression

乱搞 卡诺图

 

Body

Source

http://acm.hdu.edu.cn/showproblem.php?pid=4413

Description

给定N变量的所有2^N最小项,求一个符合所有最小项的最优美(长度最短的情况下字典序最小)的与或式。

Solution

天王还是太自信了……唉……

思路其实很简单。

复习一下卡诺图吧,考虑在卡诺图上圈一些圈,这些圈(可以重叠)覆盖且仅覆盖了所有为1的最小项,表达式就是这些圈项的或。

考虑卡诺图上的某个1,则所有覆盖这个1的非极大圈都不可能是最终答案的项,反证如下:假设某个覆盖这个1的非极大圈是最终答案的项,由于圈非极大,那么它一定属于某个极大圈,显然极大圈化简出的项长度比非极大圈要小。

于是所有可能的属于最终答案的项就是卡诺图上的所有极大圈。天王的错误就在于他只求出覆盖了每个1的最大(在所有极大圈中最优美)圈,这就相当于贪心,肯定是不对的(有可能某个非最大拼上其它的会更优)。这个地方不是很容易想明白,我也是试了一些数据才知道。

所以我们就对每个1求覆盖它的所有极大圈,得到一个极大圈集合(注意unique一下)。注意每个极大圈的表达式长度一定,所以先对每个极大圈求最优表达式(sort每个与项,比较函数是str1+str2<str2+str1)。然后就是用这些极大圈求最优覆盖,这个好像没什么好方法,只能搜。对极大圈集合排序一下可以加快搜索速度。

Code

代码是在天王那个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 << '\n';
    }
    return 0;
}

参考:http://www.cnblogs.com/jffifa/archive/2012/09/23/2699253.html