算法
(DP)
f(i,j)
: 当前这个人从 (i, j)
这点开始移动的“高桥得分-青木得分”的最佳值
转移方程:$$f(i, j) = \max(a[i][j + 1] - f(i, j + 1), a[i + 1][j] - f(i + 1, j))$$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::max;
const int INF = 1001001001;
int h, w;
int a[2005][2005];
bool visited[2005][2005];
int memo[2005][2005];
int f(int i, int j) {
if (i == h - 1 and j == w - 1) return 0;
if (visited[i][j]) return memo[i][j];
visited[i][j] = true;
int res = -INF;
if (j + 1 < w) res = max(res, a[i][j + 1] - f(i, j + 1));
if (i + 1 < h) res = max(res, a[i + 1][j] - f(i + 1, j));
return memo[i][j] = res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
rep(i, h)rep(j, w) a[i][j] = s[i][j] == '+' ? 1 : -1;
int score = f(0, 0);
if (score == 0) puts("Draw");
if (score < 0) puts("Aoki");
if (score > 0) puts("Takahashi");
return 0;
}