快要省选了，需要学习一些乱搞操作。
在这里学习一下Min-Max对抗搜索。
首先了解一下Min-Max对抗搜索。
首先我们知道，对于一个零和有限信息确定性博弈游戏，我们可以将整个游戏的所有局面建成一个有向图。而在几乎所有此类游戏中，整个游戏的所有局面应当能组成一个DAG。
对于这样一个DAG，我们可以对它进行分层，最后得到的应当是一张分层图。这张分层图上的每一层象征着一方正在进行操作。
那么显然这个游戏的最终解是可以知道的。无非就是直接把整张图DFS一遍罢了。
然而，在绝大部分游戏中，这么做的复杂度都太大了，以至于根本无法接受。我们考虑一种被称为Min-Max对抗搜索的搜索方法。
我们首先定义先手方为Max方，后手方为Min方，然后设置一个搜索范围。那么每一个节点的值是这样确定的：
如果它的深度是搜索深度边缘，亦或者它干脆就是一个终止局面，那么它的值就是一个精心设计的估价函数的值。这个估价函数应当能够较好地估计整个局面倾向于哪一方。
如果这个节点是由Max方行动，那么它的值是所有子局面里的值的最大值，因为Max方会向对自己最有利的局面走。
如果这个节点是由Min方行动，那么它的值是所有子局面里的值的最小值，因为Min方会向对Max方最不利的局面，也就是对自己最有利的局面走。
这样就能够求得当前局面的权值，从而得到一个较优秀的决策支了。
本来打算学一下alpha-beta剪枝的，但是这一题好像不是很需要…
回到这一题，如果我们暴力储存每一个状态，那么很显然时间会爆炸。有没有更好的思路呢？
直觉告诉我们，一个格子放置的次序和答案是没有关系的。所以我们不妨假定当前放置的格子总是左上角的一整个块。这样状态数大概就在10^10以内了。
然而实际上并不需要这么多的状态。所以可以Hash以后用map离散化。
#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>
inline int Max(int A,int B){
return A>B?A:B;
}
inline int Min(int A,int B){
return A<B?A:B;
}
const int INF=0x3f3f3f3f;
std::tr1::unordered_map<long long,int> mp;
int a[11][11],b[11][11],f[11],n,m;
inline long long hsh(){
long long RT=0;
for(int i=1;i<=n;++i){
RT*=12;
RT+=f[i];
}
return RT;
}
inline void ahsh(long long X){
for(int i=n;i>=1;--i){
f[i]=X%12;
X/=12;
}
}
inline int dfs(long long X,bool typ){
if(mp.count(X)){
return mp[X];
}
int RT=typ?-INF:INF;
long long nw;
ahsh(X);
for(int i=1;i<=n;++i){
if(f[i]<f[i-1]){
++f[i];nw=hsh();
RT=typ?Max(RT,dfs(nw,0)+a[i][f[i]]):Min(RT,dfs(nw,1)-b[i][f[i]]);
--f[i];
}
}
return mp[X]=RT;
}
void init(){
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]);
}
}
for(int i=0;i<=n;++i){
f[i]=m;
}
mp[hsh()]=0;
printf("%d\n",dfs(0,1));
}
int main(){
init();
return 0;
}