P4363 [九省联考 2018] 一双木棋 思考过程&题解
yokai_ing
·
·
题解
一开始看到这个问题挺一筹莫展的，总觉得需要预判未来很多情况才能走出一步，所以根本不知道怎么转移。
后面发现，在规则限制下，图形有从上到下棋子单调递减的特征，且转移只能由左上往右下，并且每个状态能转移到的其他状态也很有限，所以确定是dp。
问题是状态的表示，
每次转移需确定先后手，所以记录当前行棋子数奇偶性应该是需要的。在从上往下递减的前提下，直接每一位表示含有的棋子数太浪费，不可行。从上到下递减的性质可以利用，但我想不出来。
于是，我灵机一动（翻开题解），发现n行棋子数可以压到一行表示，即对于一个为1的位k，其[0,k]位间，1的总数就是(n-当前行数)，0的总数就是其棋子数,因为递减，所以不会出现串味，所以一个状态的表示也是唯一的，这就是状态。
但正面做要倒着做，还不如搜索写的顺手，判断也多，所以考虑在dfs时dp：
转移就显而易见了，找到每个前1后0的地方，交换一下就是其未来的状态了。注意可以顺手提前处理有用的状态和该状态下的一些有用信息来更方便写，方程如下(先手）：
f_{s_x}=max~{f_{s_x+2^{d_{x,i}}}+a_{i,sum_{x,i}}}
具体见代码：
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=12;
#define MAXN 200010
#define ll long long
ll f[1<<20];
int tot,sum[MAXN][12];
int n,m,a[N][N],b[N][N];
int s[MAXN],d[MAXN][12];
int c[MAXN],ds[1<<20],vis[MAXN];
void init(){
for(int i=1;i<(1<<(n+m));i++)
{
int x=__builtin_popcount(i);
if(x!=n)continue;
s[++tot]=i;
ds[i]=tot;
int now=n,ss=0;
for(int j=0;j<n+m;j++)
{
if((i>>j)&1){
d[tot][now]=j;
sum[tot][now--]=ss;
c[tot]=(c[tot]+ss)%2;
}else ss++;
}
c[tot]^=1;
}
}
ll dfs(int x)
{
if(vis[x])
return f[s[x]];
vis[x]=1;
f[s[x]]=(c[x]?-1ll:1ll)*1e18;
for(int i=1;i<=n;i++)
{
int p=d[x][i],q=sum[x][i];
if(s[x]&(1<<(p+1))||q>=m)
continue;
if(!c[x])
f[s[x]]=min(f[s[x]],dfs(ds[s[x]+(1<<p)])-b[i][q+1]);
else f[s[x]]=max(f[s[x]],dfs(ds[s[x]+(1<<p)])+a[i][q+1]);
}
return f[s[x]];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
init();
f[s[tot]]=0,vis[tot]=1;
printf("%lld\n",dfs(1));
return 0;
}
```