一双木棋（chess）

菲菲和牛牛在一块

棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。

棋盘的每个格子上，都写有两个非负整数，从上到下第 $A_{i,j}Ai,j、B_{i,j}Bi,j。在游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的 A_{i,j}Ai,j 之和，牛牛的得分是所有有白棋的格子上的 B_{i,j}Bi,j 的和。$

菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都采用最优策略且知道对方会采用最优策略，那么，最终的结果如何。

从标准输入中读入数据。

输入第一行包含两个正整数 $A_{i,j}Ai,j。$

接下来 $B_{i,j}Bi,j。$

输出到标准输出中。

输出一个整数，表示菲菲的得分减去牛牛的得分的结果。

样例输入

样例输出

样例解释

Explanation 1

棋盘如图所示，双方都采用最优策略时，棋局如下：

菲菲下在第
牛牛下在第
菲菲下在第
牛牛下在第
菲菲下在第
牛牛下在第
填满棋盘，游戏结束，盘面如下。

Explanation 2

菲菲的得分为：

对于所有的测试数据， $A_{i,j}, B_{i,j} leq 100000n,m≤10,Ai,j,Bi,j≤100000。$

对于编号为奇数的测试点,保证所有的 $B_{i,j} = 0Bi,j=0。$

测试点

CCF 2018省选Day1

Solution

一个合法的状态一定是一个左上角，也就是一条从左下走到右上的路线。

那么就是C（20，10）似乎不大。

考虑用hash压缩状态，记搜转移。

似乎跑的非常慢，还好oj快

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#define ll unsigned long long 
#define p 793999
using namespace std;
int n,m,a[12][12],b[12][12],tmp[12];
unordered_map<ll,int>f,g,s[12];
ll get(){
    ll H=0;
    for(int i=1;i<=n;i++){
        H=H*p+tmp[i];
    }
    for(int i=1;i<=m;i++)s[i][H]=tmp[i];
    return H; 
}
void dfs(int x,ll k){
    if(x==n*m+1){f[k]=0;return;}
    if(g[k])return ;g[k]=1;
    for(int i=1;i<=m;i++)tmp[i]=s[i][k];
    int Mx=-1e9,Mi=1e9;
    if(tmp[1]<m){
        tmp[1]++;ll nx=get();dfs(x+1,nx);
        Mx=max(Mx,f[nx]+a[1][tmp[1]]); 
        Mi=min(Mi,f[nx]-b[1][tmp[1]]);
        tmp[1]--;
    }
    for(int i=1;i<=n;i++){
        if(tmp[i]<tmp[i-1]){
            tmp[i]++;ll nx=get();dfs(x+1,nx);
            Mx=max(Mx,f[nx]+a[i][tmp[i]]); 
            Mi=min(Mi,f[nx]-b[i][tmp[i]]);
            tmp[i]--;
        }
    }
    if(x&1)f[k]=Mx;else f[k]=Mi;
}
int main(){
    cin>>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]);
    dfs(1,0);
    cout<<f[0]<<endl;
    return 0;
}