■問題
Problem Statement
すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には A個の物が積まれており、上から i 番目のものの価値はai である。左の山にはB 個の物が積まれており、上からi 番目のものの価値はbi である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。両方の山が空であれば、ゲームを終了する。
・片方の山が空であれば、空でないほうの山の一番上のものをとる。
・両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。
・両者が最善を尽くしたとき、すぬけ君の取るものの価値の合計を求めよ。
https://atcoder.jp/contests/tdpc/tasks/tdpc_game
■ポイント
・ゲーム結果は山からカードをすべて取り終えた、最終状態で決まる。そのため、最終状態から逆算してスコアが最大になるか、調べていく。
・自分の得点を増やすことと、相手の得点を減らすことは同義。
・相手の得点を最小にすることは、自分の得点を最大にすること、と言い換えることもできる。
# include <bits/stdc++.h>
using namespace std;
int main() {
int A,B; cin >> A >> B;
vector<int> a(A),b(B);
for(int i=0; i<A; i++) cin >> a[i];
for(int i=0; i<B; i++) cin >> b[i];
//dp[i][j] := Aからi個、Bからj個撮った状態から最後までの先行の最適スコア
vector<vector<int>> dp(A+1,vector<int>(B+1));
dp[A][B] = 0;
for(int i=A; i>=0; i--){
for(int j=B; j>=0; j--){
if(i == A && j == B) continue;
//先行の番のとき
//スコアが最大となるように
if((i+j)%2 == 0){
if(i==A) dp[i][j] = b[j] + dp[i][j+1];
else if(j == B) dp[i][j] = a[i] + dp[i+1][j];
else dp[i][j] = max(a[i] + dp[i+1][j],b[j] + dp[i][j+1]);
}
//後攻の番の時
//スコアが最小となるように(自分の番じゃないから点数が入らない)
else{
if(i==A) dp[i][j] = dp[i][j+1];
else if(j == B) dp[i][j] = dp[i+1][j];
else dp[i][j] = min(dp[i+1][j],dp[i][j+1]);
}
}
}
cout << dp[0][0] << endl;
}