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[<<][];
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=,Y_table=,Z_table=;
for(int i=;i<;++i)
{
if(i&(<<)) X_table+=(<<i);
if(i&(<<)) Y_table+=(<<i);
if(i&(<<)) Z_table+=(<<i);
}
add(,X_table,"x");
add(,Y_table,"y");
add(,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==)
{
add(,u.table^FULL,"!"+u.exp);
add(,u.table,u.exp);
}
if(u.level==)
{
for(int i=;i<=FULL;++i)
{
if(!dp[i][].empty())
{
add(,i&u.table,dp[i][]+"&"+u.exp);
add(,i&u.table,u.exp+"&"+dp[i][]);
}
}
add(,u.table,"("+u.exp+")");
add(,u.table,u.exp);
}
if(u.level==)
{
for(int i=;i<=FULL;++i)
{
if(!dp[i][].empty())
{
add(,i|u.table,dp[i][]+"|"+u.exp);
add(,i|u.table,u.exp+"|"+dp[i][]);
}
}
add(,u.table,"("+u.exp+")");
}
}
}
void work()
{
int n;
scanf("%d",&n);
string s;
for(int i=;i<=n;++i)
{
cin>>s;
// cout<<"s="<<s<<endl;
int state=;
for(int j=;j<;++j)
{
if(s[j]=='') state|=(<<j);
}
//printf("state=%d\n",state);
cout<<dp[state][]<<endl;
}
}
int main()
{
pre();
work();
return ;
}