Typical DP Contest B:ゲーム

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_game

解法

mini-max法をメモ化するなど。

Score=(先手の得点)-(後手の得点)
として、先手はScoreを最大化、後手はScoreを最小化しようとするやつ。

コード

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

int Z;
int N,M;
vector<int>A,B;
int dp[1001][1001];

int calc(int a,int b){
    if(a==N&&b==M)return 0;
    if(~dp[a][b])return dp[a][b];
    int ret;
    if((a+b)&1){
        ret=INT_MAX;
        if(a!=N)ret=min(ret,calc(a+1,b)-A[a]);
        if(b!=M)ret=min(ret,calc(a,b+1)-B[b]);
    }
    else{
        ret=INT_MIN;
        if(a!=N)ret=max(ret,calc(a+1,b)+A[a]);
        if(b!=M)ret=max(ret,calc(a,b+1)+B[b]);
    }

    return dp[a][b]=ret;
}

int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        int x;cin>>x;A.push_back(x);
        Z+=x;
    }
    for(int i=0;i<M;i++){
        int x;cin>>x;B.push_back(x);
        Z+=x;
    }
    fill_n(*dp,1001*1001,-1);
    cout<<(calc(0,0)+Z)/2<<endl;
    return 0;
}