Description：

在一个 $n\times m$ 的棋盘上，两个人轮流落子，每个位置第一个人落子有一个分数，第二个人落子有一个分数，每个人都想让自己的分数减对方的分数尽量大，问最后先手减后手的分数。

$1\leqslant n,m\leqslant 10$

Solution：

$n$ 和 $m$ 都很小，可以考虑状压，类似 SCOI2008 奖励关 ，正着推的话不知道后手的操作，可能会因为后手可以在之后进行一些操作而变换这一步的策略，而这之前的得分情况都是确定的，所以我们可以考虑倒着推，即从所有格子都已经选完到游戏开始，状压一下边界线，即向上是一向右是零，每次找到一个可以放棋子的位置从那之后转移过来，状态定义就是当前这个人的分减对手得分，方程为 $f[i]=\max(a/b[i][j]-f[nxt])$ ，注意一些细节比如说如何确定这个位置的具体坐标，这个可以让当前格子在边界线上移动，还有这个格子应该用哪个得分。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 11

int a[2][MAXN][MAXN];

int state[1 << (MAXN * 2)],tot = 0;

int f[1 << (MAXN * 2)];

int w[1 << (MAXN * 2)];

int cnt(int k)

{

	int res = 0;

	while(k > 0)

	{

		if(k & 1)++res;

		k = k >> 1;

	}

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&a[0][i][j]);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&a[1][i][j]);

	memset(f,0xc0,sizeof(f));

	f[(1 << n) - 1] = 0;

	for(int i = 0;i <= (1 << (n + m)) - 1;++i)

		if(cnt(i) == n)state[++tot] = i;

	for(int i = 2;i <= tot;++i)

		for(int k = 1;k < n + m;++k)

			if(((state[i] >> (k - 1)) & 1) == 0 && ((state[i] >> k) & 1) == 1)

				w[state[i]] = w[state[i] ^ (1 << (k - 1)) ^ (1 << k)] + 1;

	for(int i = 2;i <= tot;++i)

	{

		int s = state[i];

		int type = (n * m - w[state[i]]) % 2;

		int curx = 1,cury = m;

		for(int k = 1;k < n + m;++k)

		{

			if(((state[i] >> (k - 1)) & 1) == 0 && ((state[i] >> k) & 1) == 1)

			{

				f[state[i]] = max(f[state[i]],a[type][curx][cury] - f[state[i] ^ (1 << (k - 1)) ^ (1 << k)]); 

			}

			if((state[i] >> (k - 1)) & 1)++curx;

			else --cury;

		}

	}

	cout << f[((1 << n) - 1) << m] << endl;

	return 0;

}