AOJ 1353: Sweet War

dp[i][j][k]: i番目のお菓子でkさんが始めてから先手の人がj得て終わるためには(先手の人のエネルギー)-(後手の人のエネルギー)が何以上/以下であればよいか

見てのとおり遷移が複雑です。次の2通りの遷移があります。

• i番目をkさんは選ぶ。相手のdpテーブルから先手の人がj得て終わる状態にできない(相手が余分に取ってしまうとかで)ような手を起こさないためにはどのくらいエネルギーが必要かを計算できます。
• i番目をkさんじゃないほうに取らせてi+1番目で自分の番をやる(↑より遷移が楽ですが、自分のほうがエネルギーが多い状況にしないといけません。また、1だけパスする分のエネルギーを消費します。)

こういう複雑な深い思考を要する問題は苦手。

#include<stdio.h>
#include<algorithm>
using namespace std;
int r[200];
int s[200];
long long dp[200][200][2];
int v[200][200][2];
int n;
long long INF=99999999999999LL;
int sum;
long long solve(int a,int b,int c){
	if(v[a][b][c])return dp[a][b][c];
	v[a][b][c]=1;
	if(a==n){
		if(b==0){
			if(c==0)dp[a][b][c]=-INF;
			else dp[a][b][c]=INF;
		}else{
			if(c==0)dp[a][b][c]=INF;
			else dp[a][b][c]=-INF;
		}
	//	printf("%d %d %d: %lld\n",a,b,c,dp[a][b][c]);
		return dp[a][b][c];
	}
	if(c==0)dp[a][b][c]=INF;
	else dp[a][b][c]=-INF;
	if(b-s[a]*(1-c)>=0){
		//long long t=solve(a+1,b-s[a]*(1-c),!c);
		if(c==0){
			long long t=-INF;
		//	printf("%d\n",b-s[a]);
			for(int i=0;i<b-s[a];i++){
				//if(i>sum)printf("ng\n");
				t=max(t,solve(a+1,i,1)+1);
			}
			dp[a][b][c]=min(dp[a][b][c],t-r[a]);
		}else{
			long long t=INF;
			for(int i=b+1;i<=sum;i++)t=min(t,solve(a+1,i,0)-1);
			dp[a][b][c]=max(dp[a][b][c],t+r[a]);
		}
	}
	if(b-s[a]*c>=0){
		long long t=solve(a+1,b-s[a]*c,c);
		if(c==0){
			t=max(t+r[a],0LL);
			dp[a][b][c]=min(dp[a][b][c],t+1);
		}else{
			t=min(t-r[a],0LL);
			dp[a][b][c]=max(dp[a][b][c],t-1);
		}
	}
//	printf("%d %d %d: %lld\n",a,b,c,dp[a][b][c]);
	return dp[a][b][c];
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	n=a;
	for(int i=0;i<a;i++)scanf("%d%d",r+i,s+i);
	sum=0;
	for(int i=0;i<a;i++)sum+=s[i];
	for(int i=sum;i>=0;i--){
		if(b-c>=solve(0,i,0)){
			printf("%d %d\n",i,sum-i);return 0;
		}
	}
	
}