题解 CF913E 【Logical Expression】
xtx1092515503
2021-01-10 19:22:11
一种打表优化的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$ 数组中：
```cpp
#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;
}
*/
```