# 星星灰暗着。

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

posted on 2018-04-10 20:52:59 | under 题解 |

## 写了个比较通俗易懂的。

#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状态的答案
}