Typical DP Contest B - ゲーム
問題リンク : B: ゲーム - Typical DP Contest | AtCoder
解法 :
dp[i][j] := 左の山の残りがi個、右の山の残りがj個の時の(すぬけのターン)最大or(すめけのターン)最小値
両方の山が0を初期状態とし、1手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; }