题解 P4363 【[九省联考2018]一双木棋chess】

题解在博客[食用](http://www.cnblogs.com/YoungNeal/p/8746362.html)效果更佳哦~ ## Solution 考场上没想出来写的 30 分暴力诶 没想到现在就已经会了 我们定义某一时刻棋盘上的落子情况为当前的**状态** 定义 $s$ 为初状态，即棋盘上还没有落子 定义 $t$ 为末状态，即棋盘上已经落完子 不难证明，合法的状态小于二十万种 那么先 $HASH$ 一下每个状态，令其唯一对应一个正整数 对于每一个状态，我们可以知道它是从哪些状态转移来的 定义 $num[i]$ 表示 $i$ 状态落了多少子，方便判断当前是该先手还是该后手。 我们 $dp$ 要倒着推，因为如果正着推，有可能出现当前虽然求出了最大价值，但是却不是他们的最优策略的情况。 所以定义 $f[i]$ 表示从状态 $i$ 到末状态 $t$ 先手减后手的最大价值 $f[t]$ 初值为$0$，$f[1]$ 即为答案 但是怎么求中间状态 $f[i]$ 的值呢？ 之前提到过，可以求出 $i$ 状态是由 哪些状态转移来的，假设有一个状态为 $j$ 可以转移到 $i$ 我们用 $num$ 数组求出在状态 $j$ 时是先手下了还是后手下了最后一个棋子，然后分情况讨论 如果是先手：考虑后手的最优策略，显然是想让 $f[i]$ 最小，所以 $f[i]=min{f[j]-b[x][y]}$，$x$、$y$ 是 $j$ 转移到 $i$ 状态落子的横纵坐标 同理，如果为后手：那么 $f[i]$ 最大的转移方程是 $f[i]=max{f[j]+a[x][y]}$，$x$、$y$ 的意义跟上面一样 那我们现在就剩最后一个问题了：怎么进行转移呢？ 我这里利用了拓扑序进行转移：如果一个状态被所有的后续状态遍历完并求出最优解后，就将其 $push$ 进队列里，让它去转移状态即可。 最坏情况时间复杂度 O(18万*180万） 但是开氧气优化跑的贼快，最慢的点 $300ms$ ~~(反正省选也开 O2 不算作弊)~~ ## Code ``` // By YoungNeal #include<map> #include<queue> #include<cstdio> #include<cctype> #define N 400005 #define int long long #define mod 1000000007 using namespace std; int head[N]; int cnt,s,t; int n,m,tot; int qp[N][15]; int f[N],fz[15]; int deg[N],num[N]; int a[15][15],b[15][15]; map<int,int> mp; queue<int> topo; struct Edge{ int to,nxt,disa,disb; }edge[N*10]; void add(int x,int y,int z,int p){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; edge[cnt].disa=z; edge[cnt].disb=p; head[x]=cnt; } void hsh(int x){ int d=0;tot++; for(int i=1;i<=n;i++) d=d*15+fz[i],d%=mod,qp[tot][i]=fz[i]; mp[d]=tot; num[tot]=x; if(num[tot]&1) f[tot]=2e18; else f[tot]=-2e18; } void dfs(int now,int lim,int num){ if(now>n){ hsh(num); return; } for(int i=0;i<=lim;i++) fz[now]=i,dfs(now+1,i,num+i); } void _find(){ int x=0,y=0; for(int i=1;i<=n;i++) y=y*15+m,y%=mod; s=mp[x],t=mp[y]; } void read(int &x){ x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); } signed main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) read(a[i][j]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) read(b[i][j]); } dfs(1,m,0); _find(); f[t]=0; for(int i=2;i<=tot;i++){ for(int j=n;j;j--){ if(qp[i][j]==qp[i][j+1]) continue; int x=0;int idx=j,idy=qp[i][j]; for(int p=1;p<=n;p++){ if(p==j) x=x*15+qp[i][j]-1,x%=mod; else x=x*15+qp[i][p],x%=mod; } if(num[i]&1) add(i,mp[x],a[idx][idy],0); else add(i,mp[x],0,b[idx][idy]); deg[mp[x]]++; } } topo.push(t); while(topo.size()){ int u=topo.front();topo.pop(); for(int i=head[u];i;i=edge[i].nxt){ int to=edge[i].to; if(num[to]&1) f[to]=min(f[to],f[u]-edge[i].disb); else f[to]=max(f[to],f[u]+edge[i].disa); deg[to]--; if(!deg[to]) topo.push(to); } } printf("%lld\n",f[1]); return 0; } ```