【笔记】轮廓线dp

参考
用沿着格子边的线刻画一条轮廓线，状态满足字典序，可以直接递推

[九省联考 2018] 一双木棋 chess
这种类似min-max博弈的递推思路和期望dp挺类似的，设 f[s][0/1] 表示当前棋盘状态 s，当前轮到玩家 0/1 时，当前玩家之后可以获得的最大的自己收益与对方的差值，若 s 经过一步到达 ss，则有 $$f[s][0/1] = max\lbrace A[x,y][0/1] - f[ss][1/0]\rbrace$$
对当前的 s，只有对应轮到的那个玩家才能进行递推
实际上应该写记忆化搜索的，复杂度就从2的幂变成组合数了，但是反正数据不大（

#include 
#include 
#include 
using namespace std;
const int INF = 1048580;
int N, M, A[10][10][2], f[INF][2];
bool ok(int s)
{
	int b=0; while (s) b++, s-=(s&(-s));
	return b==N;
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++) scanf("%d", &A[i][j][0]);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++) scanf("%d", &A[i][j][1]);
	//memset(f, 0xc0, sizeof(f));
	//f[(1<