题解 P4363 【[九省联考2018]一双木棋chess】
teafrogsf
2018-04-10 20:52:59
## 写了个比较通俗易懂的。
首先我们可以发现，存每个位置的状态显然是不行的。而作者又比较弱不会轮廓线上DP，所以只会写爆搜。
我们可以存储每一行放了多少个棋子，因为显而易见地，这些棋子都要放到最左边，所以可以很方便地表示一整个棋盘。
然后开始简易的对抗搜索，先手时取max，后手时取min，理解方法许多题解都有提到，不再赘述。
只需要每次判断在这一行下子是否可行，然后进行搜索即可。
因为直接暴力存储13进制数的原因，跑的比较慢，最大点0.1s。~~对于我这样的juruo来说可以了~~
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<tr1/unordered_map>
#define neko 12
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
typedef long long ll;
int n,m,a[neko][neko],b[neko][neko],num[neko];
ll rdx=13;
std::tr1::unordered_map<ll,int>ht;
ll zip()//加密
{ll x=0;f(i,1,n)x=x*rdx+1ll*num[i];return x;}
void unzip(ll x)//解密
{rf(i,n,1)num[i]=x%rdx,x/=rdx;}
int dfs(ll now,bool hand)//hand=1 先手 =0 后手
{
if(ht.count(now))return ht[now];
unzip(now);int ans=hand?(-0x3f3f3f3f):(0x3f3f3f3f);ll aft;//注意初始值
f(i,1,n)
{
if(num[i]<num[i-1])
{
++num[i],aft=zip();
if(hand)ans=chkmax(ans,dfs(aft,0)+a[i][num[i]]);
else ans=chkmin(ans,dfs(aft,1)-b[i][num[i]]);
--num[i];
}
}ht[now]=ans;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
f(i,1,n)
f(j,1,m)
scanf("%d",&a[i][j]);
f(i,1,n)
f(j,1,m)
scanf("%d",&b[i][j]);
f(i,0,n)num[i]=m;
ht[zip()]=0;
dfs(0,1);return printf("%d\n",ht[0]),0;//输出0状态的答案
}
```