Skip to content

题解-AT_abc201_d

Posted on:2023年7月8日 at 11:58

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

题面大意

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

(在模拟赛甚至想出来了是我没想到的)

解题思路

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

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

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

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

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

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

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

fi1,j=min{(fi,j+map_i,j)} f*{i-1,j} = \min\{-(f*{i,j}+map\_{i,j})\}
fi,j1=min{(fi,j+map_i,j)} f*{i,j-1} = \min\{-(f*{i,j}+map\_{i,j})\}

但是,我们应该倒序遍历地图,因为正序遍历会出现后效性,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;
}


在 Rickyxrc's blog 出现的文章,若无特殊注明,均采用 CC BY-NC-SA 4.0 协议共享,也就是转载时需要注明本文章的地址,并且引用本文章的文章也要使用相同的方式共享。