TypicalDPContest B:ゲーム

典型DPコンテストB問題。
http://tdpc.contest.atcoder.jp/tasks/tdpc_game

自分は自分の得点を最大化する。
相手は相手の得点を最大化する→相手は自分の得点を最小化する
と言い換えることができる。

#include<iostream>
#include<vector>
#include<algorithm>
#define INF (1<<29)
 
using namespace std;
 
int A,B,memo[1001][1001][2];
vector<int>a,b;
 
int rec(int idA,int idB,int turn){
 
  if(idA==A && idB==B)return 0;
  if(memo[idA][idB][turn]<INF)return memo[idA][idB][turn];
 
  int res;
  if(turn==0){
    res=0;
    if(idA<A)res=max(res,rec(idA+1,idB,1)+a[idA]);
    if(idB<B)res=max(res,rec(idA,idB+1,1)+b[idB]);
  }
  else if(turn==1){
    res=INF;
    if(idA<A)res=min(res,rec(idA+1,idB,0));
    if(idB<B)res=min(res,rec(idA,idB+1,0));
  }
 
  return memo[idA][idB][turn]=res;
}
 
int main(void){
 
  fill(*memo[0],*memo[1001],INF);
 
  cin >> A >> B;
  a.resize(A);
  b.resize(B);
  for(int i=0;i<A;i++)cin >> a[i];
  for(int i=0;i<B;i++)cin >> b[i];
 
  cout << rec(0,0,0) << endl;
 
  return 0;
}