AOJ 2741 Invisible

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2741

解法

メモ化再帰で解ける．
memo[si][sj][i][j][turn][pass] := a(si)からa(i-1)，b(sj)からb(j-1)までスタックに積まれていて，手番がturnかつパスの状態がpassであるときの最大値．(pass == 1 ならば，スタックが空の状態で一回パスされたことを表す)

先攻は score_a - score_b が最大になるように，後攻は最小になるようにする．

パスしたときに何点入るかだが，よく考えてみると，スタックにある a のカードと b のカードの枚数の差は高々1枚であるので，丁寧に場合分けすると得点が計算できる．(累積和使ったほうがスッキリしたかも？)
あとは普通に遷移を書くだけ．

ソースコード

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

constexpr int INF = 1e9;

int N, M;
int memo[51][51][51][51][2][2];
vector<int> a, b;

int calc(int si, int sj, int i, int j, int turn) {
    int score_a = 0, score_b = 0;
    if(turn == 0) {
        if(i - si < j - sj) {
            if(b[sj] != -1) {
                score_b = b[sj];
            }
            sj += 1;
        }
        for(int k=0; k<i-si; ++k) {
            if(a[si+k] == -1) {
                score_b = 0;
            } else {
                score_a += a[si+k];
            }
            if(b[sj+k] == -1) {
                score_a = 0;
            } else {
                score_b += b[sj+k];
            }
        }
    } else {
        if(j-sj < i-si) {
            if(a[si] != -1) {
                score_a = a[si];
            }
            si += 1;
        }
        for(int k=0; k<i-si; ++k) {
            if(b[sj+k] == -1) {
                score_a = 0;
            } else {
                score_b += b[sj+k];
            }
            if(a[si+k] == -1) {
                score_b = 0;
            } else {
                score_a += a[si+k];
            }
        }
    }
    return score_a - score_b;
}

// [si, i), [sj, j)
int dp(int si, int sj, int i, int j, int turn, int pass) {
    int& r = memo[si][sj][i][j][turn][pass];
    if(r != INF) {
        return r;
    }
    if(turn == 0) {
        r = -INF;
        if(pass == 1) {
            r = max(r, 0);
        } else {
            r = max(r, dp(i, j, i, j, 1, (i == si && j == sj)) + calc(si, sj, i, j, 0));
        }
        if(i < N) {
            r = max(r, dp(si, sj, i+1, j, 1, 0));
        }
    } else {
        r = INF;
        if(pass == 1) {
            r = min(r, 0);
        } else {
            r = min(r, dp(i, j, i, j, 0, (i == si && j == sj)) + calc(si, sj, i, j, 1));
        }
        if(j < M) {
            r = min(r, dp(si, sj, i, j+1, 0, 0));
        }
    }
    return r;
}

int main() {
    cin >> N >> M;
    a.resize(N);
    b.resize(M);
    for(int i=0; i<N; ++i) {
        cin >> a[i];
    }
    for(int i=0; i<M; ++i) {
        cin >> b[i];
    }
    fill(memo[0][0][0][0][0], memo[50][50][50][50][2], INF);
    cout << dp(0, 0, 0, 0, 0, 0) << endl;
}