题解 P4363 【[九省联考2018]一双木棋chess】
YoungNeal
2018-04-08 19:01:37
题解在博客[食用](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;
}
```