2738 Two Ends

問題概要

n枚のカードが一列に並んでいる。
二人のプレイヤーが交互に両端のどちらかのカードを、カードがなくなるまで取っていく。
プレイヤーの得点は、プレイヤーが取ったカードにかかれた数字の和である。

先攻のプレイヤーは最適な戦略を、後攻のプレイヤーは両端のカードのうち大きいほう（同じ場合は左端）を取るという戦略を取ったとき、
後攻のプレイヤーが何点負けるかを出力せよ。

n≦1000, nは偶数とする。

解法

問題文が凄く理解しにくかった……

dp[i][j]を、先手手番で、カードi枚目からj枚目までが残っているときの最大の点差とする。
すると、先手が左側を取ったときと右側を取ったときで場合わけできて漸化式が立つのでDPできる。

ソースコード

int G,n,cd[1000];
int dp[1000][1000];

int main()
{
	while(scanf("%d",&n),n){
		rep(i,n)scanf("%d",cd+i);
		rep(i,n)rep(j,n)dp[i][j]=i==j+1?0:-inf;
		for(int w=2;w<=n;w++)rep(l,n-w+1){
			int r=l+w-1;
			int a=cd[l]+(cd[l+1]>=cd[r]?dp[l+2][r]-cd[l+1]:dp[l+1][r-1]-cd[r]);
			int b=cd[r]+(cd[l]>=cd[r-1]?dp[l+1][r-1]-cd[l]:dp[l][r-2]-cd[r-1]);
			dp[l][r]=max(a,b);
		}
		printf("In game %d, the greedy strategy might lose by as many as %d points.\n"
,++G,dp[0][n-1]);
	}
	return 0;
}