题解 CF913E 【Logical Expression】

· · 题解

一种打表优化的DP做法。

首先，观察到所有可能的输入串数量不超过 2^8=256 种，就可以往打表方向想了。

然后，我们发现，假设一种运算，其取值表为一个串 a，另一种运算的取值表为串 b，则如果我们把这两种运算用一种 operator 怼一块，其最终效果就相当于把 a 串和 b 串怼一块。

于是我们发现，只需要维护一个运算的取值表就可以来表示一种运算。

但是，我们发现，仅维护取值表，表示运算本身是可以的，但是在合并两种运算的时候，不知道要不要加括号。

于是我们便得额外再设一维，表示其最后一次进行的运算是什么。以 0 表示 or 运算，1 表示 and 运算，2 表示 not 运算，3 表示里面是一个常数。这样，如果一个优先级大的运算符被加在了比它小的运算后面，运算要加括号；被加在了不大于它的运算前面，也要加括号。

我们设 f[i][j] 表示若运算的取值表是 i，外层运算符是 j，其字典序最小的串是什么（即，储存的值是一个 string）。

我们并不知道DP顺序是什么；但是，仿照Bellman-Ford的思想，我们完全可以多跑几轮，每一轮枚举两个运算拼一起，这样多拼几次，总会把所有东西都变成稳定态。

猜想可得轮数不会太大；我跑了 20 轮就够了。

因为我们的目标是打表，所以也没必要使用什么奇技淫巧来优化，反正这么没加任何优化地写下来，最终也在 20s 内就把表打完了。假如不想打表的话，就还要费尽心思优化DP，不如打表来得爽（

打表部分的代码，最终答案被存到了 r 数组中：

#include<bits/stdc++.h>
using namespace std;
string f[256][4];//the minimum of data i, with overall state j(0:or 1:and 2:not 3:const) 
map<string,int>mp;
string s[256],r[256];
string match(pair<string,int>x,pair<string,int>y,int op){
//  cout<<x.first<<' '<<y.first<<' '<<op<<'=';
    if(op>x.second)x.first="("+x.first+")";
    if(op>=y.second)y.first="("+y.first+")";
//  cout<<x.first+(op==1?'&':'|')+y.first<<endl;
    return x.first+(op==1?'&':'|')+y.first; 
}
string rev(pair<string,int>x){
    if(x.second>=2)return "!"+x.first;
    return "!("+x.first+")";
}
void chmn(string &x,string y){if(!y.empty()&&(x.empty()||x.size()>y.size()||x.size()==y.size()&&x>y))x=y;}
int main(){
    for(int i=0;i<256;i++){
        for(int j=7;j>=0;j--)s[i]+='0'+((i>>j)&1);
        mp[s[i]]=i;
    }
    f[mp["00001111"]][3]="x";
    f[mp["00110011"]][3]="y";
    f[mp["01010101"]][3]="z";
    for(int stp=0;stp<=20;stp++){
        printf("%d\n",stp);
        for(int i=0;i<256;i++)for(int j=0;j<256;j++)for(int ii=0;ii<4;ii++)for(int jj=0;jj<4;jj++){
            if(f[i][ii].empty()||f[j][jj].empty())continue;
            chmn(f[i|j][0],match(make_pair(f[i][ii],ii),make_pair(f[j][jj],jj),0));
            chmn(f[i&j][1],match(make_pair(f[i][ii],ii),make_pair(f[j][jj],jj),1));
        }
        for(int i=0;i<256;i++)for(int ii=0;ii<4;ii++){
            if(f[i][ii].empty())continue;
            chmn(f[(~i)&255][2],rev(make_pair(f[i][ii],ii)));
        }
    }
    for(int i=0;i<256;i++)for(int j=0;j<4;j++)chmn(r[i],f[i][j]);
    for(int i=0;i<256;i++)cout<<"\""<<r[i]<<"\","<<endl;
    int n;
    cin>>n;
    string ss;
    while(n--)cin>>ss,cout<<r[mp[ss]]<<endl;
    return 0;
}
*/