AT_abc201_d题解
题目传送门
题目大意
有两个人正在下棋，棋盘是一个 $H$ 行 $M$ 列的矩阵，矩阵中的方格可以分为两种，第一种是棋子走到这里可以为选手加分；另一种是为选手扣分。
算法判断
因为题目求谁获胜且对战双方均使用最优策略，所以题目是一个求最优解的问题。求最优解一般有暴力、贪心、二分、动态规划等做法。而这一个题目暴力会超时，二分很难找出单调性，贪心难想贪心策略，所以本题采用动态规划求解。
具体步骤：
先划分阶段：
很明显双方每走一步就可以分为一个阶段。
定义状态：
因为题目只求谁赢谁输，所以状态为双方的得分差。
分决策：
下棋有两种情况，一种是 $1$ 号选手下；第 $2$ 种是二号选手下。不难发现如果当前位置是第 $i$ 行第 $j$ 列则当 $(i+j)$ 是二的倍数时为 $2$ 号选手下，否则为 $1$ 号选手下。
状态转移方程
对哪一位选手下棋进行分开讨论，在判断当前位置的棋盘情况再取最小值即可。如果第一个玩家走到了红色格子则扣分否则加分，如果当前在第 $i$ 行第 $j$ 列，那么就可以移动到第 $i-1$ 行第 $j$ 列或者第 $i$ 行第 $j-1$ 列，对于两个位置先判断是否还在棋盘中接下来对于是蓝色格子还是红色格子分开加分就可以了。
初始值
因为状态是两人分数之差，所以最好选择倒着便利。
如果倒着便利则 $dp_{n,m}$ 为初始位置应赋值为零，其他则要赋值成一个极大值。
输出
因为状态是两人分数之差，所以只用判断结束位置的之是否大于 $0$ 即可。
代码
#include
using namespace std;
#define int long long
int n,m;
char a[2005][2005];
int dp[2005][2005];
int check(int x,int y){
if(a[x][y]=='+'){
return 1;
}
if(a[x][y]=='-'){
return -1;
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >>a[i][j];
}
}
memset(dp,0x3f,sizeof(dp));//赋初始值
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-1][j],-dp[i][j]-check(i,j));
dp[i][j-1]=min(dp[i][j-1],-dp[i][j]-check(i,j));
}
}
if(dp[1][1]>0){
printf("Aoki
");//输出结果
}
else if(dp[1][1]==0){
printf("Draw
");
}
else{
printf("Takahashi
");
}
return 0;
}
