j题目链接： http://codeforces.com/contest/913/problem/E
题意：
给你x,y,z三个变量，与& 或| 非！ 括号（） 四种运算符，规定括号和非优先级最高，其次与&，最后或|。
对于输入的真值表，输出最小字典序的逻辑表达式
挺难想的。关键点在于怎么定义状态并利用已有状态更新出新状态，并处理优先级问题。
状态转移：
对于两个表达式A1,A2及其真值表T1,T2，若没有优先级的问题，A1&A2的真值表为T1&T2,A1|A2的真值表为T1|T2,!A1的真值表为~T1。
为了解决优先级的问题，按优先级不同进行分类，以dp[i][j]存储真值表为i,优先级为j的字典序最小逻辑表达式。，操作只在相同优先级表达式之间进行，维护一个优先级之间的升降通道。
模仿dijkstra的思想，维护一个序列，每次选出字典序最小的表达式作为A1并pop掉，在dp[i][j]中枚举A2进行更新操作。
真值表共有2^(2^3)共256种，优先级共3种可能。状态数n=3*256。
每种状态至多作为A1被考虑一次，枚举A2O(n)，综合得算法复杂度O(n^2)
AC代码：
#include<bits/stdc++.h> using namespace std; const int FULL=0xFF; bool cmp(string a,string b) { if(a.length()==b.length()) return a<b; return a.length()<b.length(); } struct Expression { int table; int level; string exp; Expression(int a,int b,string c) {table=a;level=b;exp=c;} bool operator < (const Expression& b)const { if(b.exp==exp) { if(level!=b.level) return level<b.level; return table<b.table; } return cmp(exp,b.exp); } }; set<Expression> q; string dp[1<<8][3]; void add(int level,int state,string s) { if(dp[state][level].empty()||cmp(s,dp[state][level])) { dp[state][level]=s; Expression e(state,level,s); q.insert(e); } } void pre() { int X_table=0,Y_table=0,Z_table=0; for(int i=0;i<8;++i) { if(i&(1<<2)) X_table+=(1<<i); if(i&(1<<1)) Y_table+=(1<<i); if(i&(1<<0)) Z_table+=(1<<i); } add(2,X_table,"x"); add(2,Y_table,"y"); add(2,Z_table,"z"); while(!q.empty()) { set<Expression>:: iterator it; it=q.begin(); Expression u=*it; q.erase(it); // auto u=*q.begin(); // q.erase(q.begin()); if(u.level==2) { add(2,u.table^FULL,"!"+u.exp); add(1,u.table,u.exp); } if(u.level==1) { for(int i=0;i<=FULL;++i) { if(!dp[i][1].empty()) { add(1,i&u.table,dp[i][1]+"&"+u.exp); add(1,i&u.table,u.exp+"&"+dp[i][1]); } } add(2,u.table,"("+u.exp+")"); add(0,u.table,u.exp); } if(u.level==0) { for(int i=0;i<=FULL;++i) { if(!dp[i][0].empty()) { add(0,i|u.table,dp[i][0]+"|"+u.exp); add(0,i|u.table,u.exp+"|"+dp[i][0]); } } add(2,u.table,"("+u.exp+")"); } } } void work() { int n; scanf("%d",&n); string s; for(int i=1;i<=n;++i) { cin>>s; // cout<<"s="<<s<<endl; int state=0; for(int j=0;j<8;++j) { if(s[j]=='1') state|=(1<<j); } //printf("state=%d ",state); cout<<dp[state][0]<<endl; } } int main() { pre(); work(); return 0; }