Typical DP Contest B - ゲーム

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_game

解法

漸化式的にも解けるが，メモ化再帰で書くほうがわかりやすいかもしれない．
この場合，minimax法でやる．
dp[l][r] := 左の一番上が l 枚目，右の一番上が r 番目の状態から始めた時の，(その瞬間の)先手の得点 - 後手の得点の最大値
としてメモ化再帰する．
答えは sum を全カードの総和として (sum + dp[0][0]) / 2 で求まる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 1e9;

int main() {
    int A, B; cin >> A >> B;
    vector<int> a(A), b(B);
    for(auto& x : a) cin >> x;
    for(auto& x : b) cin >> x;

    const int sum = accumulate(a.begin(), a.end(), 0) + accumulate(b.begin(), b.end(), 0);

    vector<vector<int>> dp(A + 1, vector<int>(B + 1, -inf));
    function<int(int, int)> rec = [&] (int l, int r) {
        if(dp[l][r] != -inf) return dp[l][r];
        if(l == A && r == B) return dp[l][r] = 0;

        int& res = dp[l][r];
        if(l != A) res = a[l] - rec(l + 1, r);
        if(r != B) res = max(res, b[r] - rec(l, r + 1));
        return res;
    };

    cout << (sum + rec(0, 0)) / 2 << endl;
}