T1
NFLSOJ P3372 game
考虑对于 B 的行动，A 会采取怎样的策略。容易发现两人路线相交只会是一条线段，因此枚举这条线段在 B 走过的哪条线段上，记录从起点和终点分别走到每个位置的最大权值，就可以搞了。然后考虑对 B 的路径 dp，\(dp[i][j][0/ 1]\) 表示从 B 的起点走到 \((i, j)\)，最后一步是怎么过来的 这样 A 最大的最小收益。转移枚举从上面还是右边的哪个位置过来，对这一段路径算出 A 的最优收益，与前面的 dp 值取 \(\max\) 再与当前位置取 \(\min\) 转移。最优收益可以一边枚举位置一边算。与前面的 dp 值取 \(\max\) 是因为选择从 B 走过的哪一段路上过是 A 的决策，与当前 dp 值取 \(\min\) 是因为从哪个位置过来是 B 的决策。
这个 dp 的本质实际上是对于每条路径计算权值，计算的方法是把所有经过当前线段的合并计算，然后由于这些路径走到当前点的所有方案都被算过了，它们就是同一个状态了，会一起参与之后的计算。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
int a[305][305];
int p1[305][305];
int p2[305][305];
int dp[305][305][2];
int n, m;
signed main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
memset(p1, 0, sizeof p1);
memset(p2, 0, sizeof p2);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
p1[i][j] = max(p1[i - 1][j], p1[i][j - 1]) + a[i][j];
}
}
for (int i = n; i; i--) {
for (int j = m; j; j--)
p2[i][j] = max(p2[i + 1][j], p2[i][j + 1]) + a[i][j];
}
memset(dp, 63, sizeof dp);
int mx=p1[1][m-1];
for(int i=2;i<=n;i++) {
dp[i][m][1] = min(dp[i][m][1], mx+p2[i+1][m]);
mx = max(mx, p1[i][m-1]);
}
mx=p2[2][m];
for(int i=m-1;i>=1;i--) {
dp[1][i][0] = min(dp[1][i][0],mx+p1[1][i-1]);
mx = max(mx,p2[2][i]);
}
for (int i = 1; i <= n; i++) {
for (int j = m; j; j--) {
int mxv = 0;
for (int k = i + 1; k <= n; k++) {
int tmp;
tmp = max(mxv, max(p2[k + 1][j], p2[k][j + 1]) + p1[k - 1][j - 1]);
tmp = max(tmp, p1[i - 1][j] + max(p2[k][j + 1], p2[k + 1][j]));
dp[k][j][1] = min(dp[k][j][1], max(dp[i][j][0], tmp));
mxv = max(mxv, p2[k][j + 1] + p1[k][j - 1]);
}
mxv = 0;
for (int k = j - 1; k; k--) {
int tmp;
tmp = max(mxv, max(p1[i - 1][k], p1[i][k - 1]) + p2[i + 1][k + 1]);
tmp = max(tmp, p2[i][j + 1] + max(p1[i - 1][k], p1[i][k - 1]));
dp[i][k][0] = min(dp[i][k][0], max(dp[i][j][1], tmp));
mxv = max(mxv, p2[i + 1][k] + p1[i - 1][k]);
}
}
}
cout << min(dp[n][1][0], dp[n][1][1]) << "\n";
}
return 0;
}