Typical DP Contest B - ゲーム

解法

漸化式的にも解けるが,メモ化再帰で書くほうがわかりやすいかもしれない.
この場合,minimax法でやる.
memo[l][r] := 左の一番上が l 枚目,右の一番上が r 番目の状態から始めた時の,(先手の得点) - (後手の得点) の最大値(手番が先手の時)または最小値(手番が後手の時)
としてメモ化再帰する.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 1e9;
 
int rec(int l, int r, int turn, vector<int> const& a, vector<int> const& b, vector<vector<int>>& memo) {
    const int A = a.size();
    const int B = b.size();
    if(l == A && r == B) {
        return memo[A][B] = 0;
    }
    int& res = memo[l][r];
    if(res != INF) {
        return memo[l][r];
    }
    res = (turn == 0 ? -INF : INF);
    if(l < A) {
        res = rec(l+1, r, turn^1, a, b, memo) + (turn == 0 ? a[l] : -a[l]);
    }
    if(r < B) {
        if(turn == 0) {
            res = max(res, rec(l, r+1, turn^1, a, b, memo) + b[r]);
        } else {
            res = min(res, rec(l, r+1, turn^1, a, b, memo) - b[r]);
        }
    }
    return res;
}
 
int main() {
    int A, B;
    cin >> A >> B;
    vector<int> a(A), b(B);
    int sum = 0;
    for(int i=0; i<A; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    for(int i=0; i<B; ++i) {
        cin >> b[i];
        sum += b[i];
    }
    vector<vector<int>> memo(A+1, vector<int>(B+1, INF));
    int t = rec(0, 0, 0, a, b, memo);
    cout << (sum + t) / 2 << endl;
}