[AtCoder - tdpc_game] ：ゲーム 题解
一道小清新 \(dp\) 题。
定义 \(dp_{i,j}\) 为第一堆山还有 \(i\) 个物品，第二堆山还有 \(j\) 个物品，すぬけ君能取得物品的最大价值。
由于只能取两座山最上面的物品，假设当前两座山分别有 \({x,y}\) 个物品，すぬけ君选后只能有两种情况，分别为 \(dp_{i-1,j}\) 或 \(dp_{i,j-1}\)。可增加的价值分别为 \(a_i\) 和 \(b_j\)。
他想让自己的答案尽量大，应取 \(max\)。
现在该另一人选择，他取了物品后将会有 \(3\) 种情况，分别为 \(dp_{i-2,j}\)，\(dp_{i-1,j-1}\)，\(dp_{i,j-2}\)。
这 \(3\) 种情况怎么来的？现在有 \(dp_{i-1,j}\) 或 \(dp_{i,j-1}\) 两种情况，另一人在两座山中再选物品。
那么，由 \(dp_{i-1,j}\) 可推出 \(dp_{i-1-1,j} = dp_{i-2,j}\) 和 \(dp_{i-1,j-1}\)。
同理，由 \(dp_{i,j-1}\) 可推出 \(dp_{i-1,j-1}\) 和 \(dp_{i,j-1-1}=dp_{i,j-2}\)。
整理可得以上 \(3\) 种情况了。
但是，由于两人都同样聪明，他会让すぬけ君接下来的答案尽量小。
所以应该以上两种情况分别取 \(min\)。
整的转移式为 \(dp_{i,j} = max(a_i + min(dp_{i-1,j-1}, dp_{i-2,j}), b_j + min(dp_{i-1,j-1},dp_{i,j-2})\)。
好了，此题就结束了。
最后贴上代码：
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
int n, m, a[N], b[N], dp[N][N];
inline ll dfs(int x, int y) {
if (!x && !y) return dp[x][y] = 0;
if (dp[x][y] != -1) return dp[x][y];
ll ret = 0, num = 1e18;
if (x >= 1 && y >= 1) num = min(num, dfs(x - 1, y - 1));
if (x >= 2) num = min(num, dfs(x - 2, y));
if (num == 1e18) num = 0;
ret = max(ret, a[x] + num);
num = 1e18;
if (x >= 1 && y >= 1) num = min(num, dfs(x - 1, y - 1));
if (y >= 2) num = min(num, dfs(x, y - 2));
if (num == 1e18) num = 0;
ret = max(ret, b[y] + num);
return dp[x][y] = ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= m; ++i)
cin >> b[i];
reverse(a + 1, a + n + 1);
reverse(b + 1, b + m + 1);
//注意翻转两个数组
memset(dp, -1, sizeof dp);
ll ans = dfs(n, m);
cout << ans << "\n";
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j)
// cout << dp[i][j] << " ";
// cout << "\n";
// }
return 0;
}