Typical DP Contest - B ゲーム

B: ゲーム - Typical DP Contest | AtCoder

• どうやって最適化戦略をとった状態を表現するのか？
• すぬけ君の得点を dp 対象にして、すぬけ君はそれを最大化・すめけ君はそれを最小化しようとする。
• 山の高さが i,j のとき先方の得点を dp 対象にして、それを最大化させるようにする。

• メモ化解法

int dp[1001][1001]; // Aがi番目,Bがj番目まで取り出された時のすぬけ君の得点の最大値
vector<int> a;
vector<int> b;
class b_game {
public:
    // すぬけ君の得点を返す
    int rec(int i, int j, int k) {
            if (dp[i][j] >= 0)
                return dp[i][j];
            int A = a.size();
            int B = b.size();

            if (i == A && j == B)
                return 0;

            int ret;
            if (k) // すめけ君のターン,すぬけ君の得点を最小化する
            {
                ret = (1<<30);
                // 取得した a[i]/b[j] はすぬけ君の得点となるので加算されない
                if (i < A)
                    ret = min(ret, rec(i+1,j,k^1));
                if (j < B)
                    ret = min(ret, rec(i,j+1,k^1));
            }
            else
            {
                ret = 0;
                if (i < A)
                    ret = max(ret, rec(i+1,j,k^1)+a[i]);
                if (j < B)
                    ret = max(ret, rec(i,j+1,k^1)+b[j]);
            }
            return (dp[i][j] = ret);
    }
    void solve(void) {
            int A,B;
            cin>>A>>B;
            a.resize(A);
            b.resize(B);
            REP(i,A) cin>>a[i];
            REP(i,B) cin>>b[i];

            memset(dp, -1, sizeof(dp));
            cout<<rec(0,0,0)<<endl;
    }
};

• DP 解法

class b_game {
public:
    void solve(void) {
            int A,B;
            cin>>A>>B;
            vector<int> a(A);
            vector<int> b(B);
            REP(i,A) cin>>a[i];
            REP(i,B) cin>>b[i];

            // sa[i] := Aの残りが i 個のときの山の得点の総和
            vector<int> sa(A+1,0);
            vector<int> sb(B+1,0);

            REP(i,A) sa[i+1] = sa[i]+a[A-1-i];
            REP(i,B) sb[i+1] = sb[i]+b[B-1-i];
            //
            // 部分問題を DP 化
            // dp[i][j] := Aがのこり i 個,Bがのこり j 個の時、自ターンの人の得点の最大値
            // この値は snuke か sumeke に関係なく自ターンの人のものになる。
            // 互いに最善を尽くすときは同じ操作になるはず。
            //
            vector<vector<int>> dp(A+1,vector<int>(B+1,0));

            // 意味的には山が空になっている状態から逆にたどる
            REP(i, A+1)
            REP(j, B+1)
            {
                int sum = sa[i]+sb[j];
                //
                // 交互にターンが切り替わるので、更新前の現在の自分の得点は
                // sum-dp[i][j] となる。
                //
                if (i < A)
                    dp[i+1][j] = max(dp[i+1][j], sum-dp[i][j]+a[A-i-1]);
                if (j < B)
                    dp[i][j+1] = max(dp[i][j+1], sum-dp[i][j]+b[B-j-1]);
            }
            cout<<dp[A][B]<<endl;
    }
};