UVA 10891 - Game of Sum DP

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832

题目大意：

有一个长度为n的整数序列，A和B轮流取数，A先取，每次可以从左端或者右端取一个或多个数，所有数都被取完时游戏结束，然后统计每个人取走的所有数字之和作为得分，两人的策略都是使自己的得分尽可能高，并且都足够聪明，求A的得分减去B的得分的结果。

思路：

跟着作者做的~这题是题很好的dp

设dp[i][j]为第i~j先手取得的最大值。

那么dp(i,j)=sum(i,j)-min{ dp(i+1,j),dp(i+2,j).....dp(j,j),   dp(i,j-1),dp(i,-2j)....dp(i,i) ,0} 0表示全部取完。

以为答案为A-B的得分，所以ans=dp[1][n]-(sum[1][n]-dp[1][n])=2*dp[1][n]-sum[1][n]；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=110;
int a[MAXN],sum[MAXN],dp[MAXN][MAXN],vis[MAXN][MAXN];
int dfs(int i,int j)
{
	if(vis[i][j]) return dp[i][j];
	vis[i][j]=1;
	int m=0;
	for(int k=i+1;k<=j;k++)  m=min(m,dfs(k,j) );
	for(int k=i;k<j;k++)  m=min(m,dfs(i,k));
	return dp[i][j]=sum[j]-sum[i-1]-m;
}
int main()
{
	int n;
	while(~scanf("%d",&n),n)
	{
		sum[0]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i]=sum[i-1]+a[i];
		}
		memset(vis,0,sizeof(vis));
		printf("%d\n",2*dfs(1,n)-sum[n]);
	}
	return 0;
}

UVA 10891 - Game of Sum DP

原文：http://blog.csdn.net/murmured/article/details/19019433