裏紙

ほぼ競プロ、たまに日記

Typical DP B - ゲーム

問題

B: ゲーム - Typical DP Contest | AtCoder

簡潔なのでまとめなくていいかと。

イデア

ゲームが進行し、Aの山の一番上がa[x]、Bの山の一番上がb[y]になっている状況を考える。

dp[x][y] := (上記のような状況での先手が取れる価値合計の最大値)として、メモ化再起による解法を考えてみた。が、敵の挙動をどのようにして処理すればいいかがわからなかったのでまとめておく。 敵の挙動は、先手の価値を全く増やさない。また、両方の山から選ぶことが出来るときには相手も最善の手を取ろうとする。つまり、これは先手側から見ると先手の価値を最小に使用する手を選択するということになるわけである。この考え方があれば、後手の挙動を再帰関数内に綺麗に収めることが出来る。

実装(C++)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int A,B;
int a[1001]={0}, b[1001]={0};

int dp[1002][1002];

int rec(int x, int y){
  int ret=0;
  if(dp[x][y]>=0) return dp[x][y];

  //両方の山が空
  if(x==A && y==B) ret = 0;
  else if((x+y)%2==0){ //先手
    if(x==A) ret = rec(x,y+1)+b[y];
    else if(y==B) ret = rec(x+1,y)+a[x];
    else ret = max( rec(x+1,y)+a[x], rec(x,y+1)+b[y] );
  }
  else{ //後手
    if(x==A) ret = rec(x,y+1);
    else if(y==B) ret = rec(x+1,y);
    else ret = min( rec(x+1,y), rec(x,y+1) );
  }

  return dp[x][y] = ret;
}

int main(int argc, char const *argv[]) {
  cin >>A >>B;
  for(int i=0; i<A; ++i) scanf("%d", &a[i]);
  for(int i=0; i<B; ++i) scanf("%d", &b[i]);
  memset(dp,-1,sizeof(dp));
  printf("%d\n", rec(0,0));
  return 0;
}