Typical DP Contest B - ゲーム

問題リンク : B: ゲーム - Typical DP Contest | AtCoder

解法 :
dp[i][j] := 左の山の残りがi個、右の山の残りがj個の時の（すぬけのターン）最大or（すめけのターン）最小値

両方の山が０を初期状態とし、１手1手戻りながら計算する

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define SUNUKE 0
#define RNG    1
#define IINF INT_MAX

int n[2],v[2][1010],dp[1010][1010];

void compute() {
  rep(i,n[0]+1) rep(j,n[1]+1) dp[i][j] = -1;
  int player = (((n[0]+n[1])&1)?SUNUKE:RNG);
  dp[0][0] = 0;
  rep(phase,n[0]+n[1]+1) {
    rep(i,n[0]+1) {
      int j = phase - i;
      if( j < 0 || j > n[1] ) continue;
      if( dp[i][j] == -1 ) continue;
      // SUNUKE 
      if( player == SUNUKE ) {
        if( i < n[0] ) {
          if( dp[i+1][j] == -1 ) dp[i+1][j] = -IINF;
          dp[i+1][j] = max(dp[i+1][j],dp[i][j]+v[0][i]);
        }
        if( j < n[1] ) {
          if( dp[i][j+1] == -1 ) dp[i][j+1] = -IINF;
          dp[i][j+1] = max(dp[i][j+1],dp[i][j]+v[1][j]);
        }
      }
      // RNG
      if( player == RNG ) { 
        if( i < n[0] ) {
          if( dp[i+1][j] == -1 ) dp[i+1][j] = IINF;
          dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
        }
        if( j < n[1] ) {
          if( dp[i][j+1] == -1 ) dp[i][j+1] = IINF;
          dp[i][j+1] = min(dp[i][j+1],dp[i][j]);
        }
      }
    }
    player = !player;
  }
  cout << dp[n[0]][n[1]] << endl;
}

int main() {
  rep(i,2) cin >> i[n];
  rep(i,2) rep(j,i[n]) cin >> v[i][n[i]-j-1];
  compute();
  return 0;
}