题解-AT_abc201_d

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

题目里写的比较显然，可以看出是一个博弈论问题。

（在模拟赛甚至想出来了是我没想到的）

解题思路

又是走棋盘又是博弈论，所以我们考虑博弈动态规划。

我们定义先手在走到 $(i,j)$ 时可以领先对手的分数。

注意我们提到的是先手不是对手。

我们这么考虑：在博弈 dp 中，先手和后手的角色在每次移动后都会互换。

所以我们领先的分数，等同于对手落后的分数。

所以我们要领先最多，不仅要得到最多分，还要让自己落后最少。

于是我们的转移方程应该是这样：

但是，我们应该倒序遍历地图，因为正序遍历会出现后效性，dp 无法处理此类问题，所以上面的的定义只能反过来。

语言表达可能不是很清楚，详见代码。

#include<stdio.h>
#include<string.h>

#define maxn 2007

int map[maxn][maxn],dp[maxn][maxn],n,m;
char ch;

int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a<b?a:b;}

int main() {
	scanf("%d%d",&n,&m);

	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			do {
				ch=getchar();
			} while(ch!='-'&&ch!='+');
			if(ch=='+')
				map[i][j] = 1;
			else
				map[i][j] = -1;
			dp[i][j] = 214748364;
		}
	dp[n][m] = 0;

	for(int i=n; i>=1; i--)
		for(int j=m; j>=1; j--)
			dp[i-1][j] = min(-(dp[i][j]+map[i][j]),dp[i-1][j]),
			dp[i][j-1] = min(-(dp[i][j]+map[i][j]),dp[i][j-1]);

	if(dp[1][1] > 0)
		puts("Aoki");
	if(dp[1][1] < 0)
		puts("Takahashi");
	if(dp[1][1] == 0)
		puts("Draw");

	return 0;
}