洛谷题单指南-状态压缩动态规划-P4363 [九省联考 2018] 一双木棋 chess
原题链接：https://www.luogu.com.cn/problem/P4363
题意解读：n*m棋盘上，每个格子有a、b两种分数，A、B轮流按最优方案（自己得分-对方得分最大化）下棋（落子位置必须左边和上边格子全有棋子），最终求A的所有得分-B的所有得分。
解题思路：
1、状态表示
先看落子规则：可落子的位置必须左边和上边所有格子全有棋子，也就是说，从落子的格子到左上角构成的矩形中，只有落子处是空的！
有了这样一个实时，落子后棋盘会形成的状态如图所示：
也就是，所有棋子都会集中在每一行的前面，并且上面行的棋子数量一定大于或等于下面行的棋子数量。
这样一来，有棋子的格子和没有棋子的格子交界处就形成了轮廓线！
沿着轮廓线，从左下角开始，到右上角为止，我们定义向右走为0，向上走为1，上图轮廓线可以表示为001011010，注意一开始从左下角是往右、再往上，因此最低两位是0、1。
这样一来，就可以状态压缩轮廓线来表示所有棋盘状态，棋盘是n*m，状态中必有n个1，m个0。
2、状态转移
定义f[s]为轮廓线状态为s时，到棋盘满时可以得到的最优得分；
当A下棋时，f[s]意味着最大值；当B下棋时，f[s]意味着最小值。
从样例出发，初始状态为：00011
第一个棋只有一种下法，落子后状态为：00101
第二个棋有两种下法，
如果下到1行2列，落子后状态为：01001
如果下到2行1列，落子后状态为：00110
经过分析，下第一步棋时，状态从00011->00101；下第二步棋时，状态从00101->01001或者00101->00110
可以得出，状态的变化就是所有的01变成10，取最优，如此以来，就可以枚举搜索来递推。
设s是上一个状态，t是将s中某一处01替换为10后的状态，也就是下一个状态，将01替换为10也意味着落地区域向右下扩张一格，设这一格的坐标是x，y
那么有：
如果当前是A下棋：f[s] = max(f[s], f[t] + a[x][y])
如果当前是B下棋：f[s] = min(f[s], f[t] - b[x][y])
3、初始化
根据定义，我们可以知道终止状态为11…100…0，n个1，m个0，且由于棋下满了，f[11…100…0] = 0
当轮到A下棋时，f[s]初始化为INF；当轮到B下棋时，f[s]初始化为-INF
4、结果
根据定义，棋盘初始状态为00…011…1，m个0，n个1，f[00…011…1]即是结果。
直接枚举不好处理，通过递归+记忆化搜索来实现DP更直观。
100分代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 10, S = 20, INF = 0x3f3f3f3f;
int a[N][N], b[N][N];
int f[1 << S];
int n, m;
//dp(s,st)表示当前轮廓线状态是s，轮到st来下棋所能得到的最优得分
//st为1表示A下棋，0表示B下棋
int dp(int s, bool st)
{
if(~f[s]) return f[s];
f[s] = st? -INF : INF; //求最大值初始化为-INF，求最小值初始化为INF
int x = n, y = 0; //x，y表示当状态从01变到10时，走的是哪个格子
for(int i = 0; i < n + m - 1; i++) //每次枚举两个二进制位i、i+1
{
if(s >> i & 1) x--; else y++; //更新可能扩展的格子坐标
if((s >> i & 3) != 1) continue; //第i+1、i位不是01，则跳过
int t = s ^ (3 << i); //将第i+1，i位的01修改成10，实现状态转移
if(st) f[s] = max(f[s], dp(t, st ^ 1) + a[x][y]);
else f[s] = min(f[s], dp(t, st ^ 1) - b[x][y]);
}
return f[s];
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> b[i][j];
memset(f, -1, sizeof(f));
f[(1 << n) - 1 << m] = 0; //初始化终止状态
cout << dp((1 << n) - 1, 1);
return 0;
}