定义二元操作符 $<$：对于两个长度都为 $n$ 的数组 $A,B$（下标从 $1$ 到 $n$），$A<B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \min(A[i], B[i])(1 \le i \le n)$。
定义二元操作符 $>$：对于两个长度都为 $n$ 的数组 $A,B$（下标从 $1$ 到 $n$），$A>B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \max(A[i], B[i])(1 \le i \le n)$。
现在有 $m(1 \le m \le 10)$个长度均为 $n$ 的整数数组 $A_0, A_1, \ldots , A_{m-1}$ 。给定一个待计算的表达式 $E$，其满足 $E$ 中出现的每个操作数都是 $A_0, A_1, \ldots , A_{m-1}$ 其中之一，且 $E$ 中只包含 $<$ 和 $>$ 两种操作符（$<$ 和 $>$ 的运算优先级相同），因此该表达式的结果值也将是一个长度为 $n$ 的数组。
特殊地，表达式 $E$ 中还可能出现操作符 $?$，它表示该运算符可能是 $<$ 也可能是 $>$。因此若表达式中有 $t$ 个 $?$，则该表达式可生成 $2^t$个可求确定值的表达式，从而可以得到 $2^t$个结果值，你的任务就是求出这 $2^t$个结果值（每个结果都是一个数组）中所有的元素的和。你只需要给出所有元素之和对 ${10}^9 + 7$取模后的值。
可以根据表达式把表达式的树建出来，发现每一位的答案独立，枚举每一位计算答案
因为只有最大值和最小值操作，每一位的答案只会有10种情况
考虑每一种答案的出现次数，状压表示答案的取值阈值，即枚举哪几个数组在该位是较小的，组成总共1024种状态，DP计算答案落入集合内时的计算次数
#include<algorithm> #include<iostream> #include<utility> #include<cstring> #include<cstdio> #include<stack> using namespace std; int n,m,map[10][50005],len,root,opt[50005],top,cnt,lc[50005],rc[50005],val[50005],dp[1024][50005][2],ans; const int mod=1e9+7; char str[50005]; stack<int>sta; pair<int,int>a[10]; inline int read(){ int w=0,f=1; char ch=0; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)w=(w<<1)+(w<<3)+ch-‘0‘,ch=getchar(); return w*f; } void solve(){if(~opt[top])val[++cnt]=-opt[top--],rc[cnt]=sta.top(),sta.pop(),lc[cnt]=sta.top(),sta.pop(),sta.push(cnt);} void dfs(int k){ if(val[k]>=0){ for(int s=0;s<(1<<m);s++) if((s>>val[k])&1)dp[s][k][0]=1; else dp[s][k][1]=1; return; } dfs(lc[k]),dfs(rc[k]); for(int s=0;s<(1<<m);s++) if(val[k]==-1)dp[s][k][1]=1ll*dp[s][lc[k]][1]*dp[s][rc[k]][1]%mod,dp[s][k][0]=(1ll*dp[s][lc[k]][0]*dp[s][rc[k]][0]%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod)%mod; else if(val[k]==-2)dp[s][k][0]=1ll*dp[s][lc[k]][0]*dp[s][rc[k]][0]%mod,dp[s][k][1]=(1ll*dp[s][lc[k]][1]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod)%mod; else dp[s][k][0]=(1ll*dp[s][lc[k]][0]*dp[s][rc[k]][0]%mod*2%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod)%mod,dp[s][k][1]=(1ll*dp[s][lc[k]][1]*dp[s][rc[k]][1]%mod*2%mod+1ll*dp[s][lc[k]][1]*dp[s][rc[k]][0]%mod+1ll*dp[s][lc[k]][0]*dp[s][rc[k]][1]%mod)%mod; } int main(){ n=read(),m=read(); for(int i=0;i<m;i++)for(int j=1;j<=n;j++)map[i][j]=read(); scanf("%s",str+1),len=strlen(str+1),opt[++top]=-1; for(int i=1;i<=len;i++){ if(str[i]==‘(‘)opt[++top]=-1; else if(str[i]==‘<‘)opt[++top]=1; else if(str[i]==‘>‘)opt[++top]=2; else if(str[i]==‘?‘)opt[++top]=3; else if(str[i]==‘)‘)--top,solve(); else val[++cnt]=str[i]-‘0‘,sta.push(cnt),solve(); } root=sta.top(),dfs(root); for(int i=1;i<=n;i++){ for(int j=0;j<m;j++)a[j]=make_pair(map[j][i],j); sort(a,a+m); for(int j=0,s=0;j<m;s|=(1<<a[j].second),j++)(ans+=1ll*(dp[s][root][1]-dp[s|(1<<a[j].second)][root][1]+mod)%mod*a[j].first%mod)%=mod; } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/JDFZ-ZZ/p/14398242.html
