Uva 10891 - Game of Sum ( 区间dp )

题目链接：

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

题目大意：

有n个数字排成一条直线，然后有两个小伙伴来玩游戏， 每个小伙伴每次可以从两端（左或右）中的任意一端取走一个或若干个数（获得价值为取走数之和）， 但是他取走的方式一定要让他在游戏结束时价值尽量的高，最头疼的是两个小伙伴都很聪明，所以每一轮两人都将按照对自己最有利的方法去取数字，请你算一下在游戏结束时，先取数的人价值与后取数人价值之差（不要求绝对值）。

题目分析：（http://hi.baidu.com/knowledgetime/item/d8ec9420a2b2f98daf48f5a4）

UVa 10891 - Game of Sum

这是一道经典动态规划试题的变形，也是拓展。我们先看看它经典原型。

题目：两个玩家A和B在玩一个取石子游戏，且每个石子都有它们各自的价值。在游戏中有这样一个规则：每次取一个石子必行从两端取，要么是最左端，要么是最右端，直到取完为止。两个玩家都非常聪明，他们每次都会去最优的结果。给他们N个石子，你能计算出玩家A，B各自的最后结果吗？假设总是玩家A先开局。

对于这题，我们考虑best[i][j]表示开局者玩家A的i到j部分得到最大和，sum[i][j]表示从i到j和,由于只能从两端取石子，要么有从最左端，要么从最右端。则有转移方程：

best[i][j]=sum[i][j]-min(best[i][j-1],best[i+1][j]); 目标状态：best[1][n]

那么推广到这题，可以取连续的，我们同样稍改变下即可。

best[i][j]=sum[i][j]-min(best[i][j-k],best[i+k][j]);{1<=k=j-i+1}.

目标状态： best[1][n]-(sum[1][n]-best[1][n])

还有显然两者的初始化：best[i][i]=a[i];

代码:

#include "uva10891.h"
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 100 + 10;
int  S[maxn], A[maxn], d[maxn][maxn], vis[maxn][maxn], n;

int dp(int i, int j)
{
	if(vis[i][j]) return d[i][j];
	vis[i][j] = 1;
	int m = 0;
	for ( int k = i + 1; k <= j; k++ ) m = min(m, dp(k, j));
	for ( int k = i; k < j; k++ ) m = min(m, dp(i, k));
	d[i][j] = S[j] - S[i - 1] - m;
	return d[i][j];
}

int main(){
	while (scanf("%d", &n) && n)
	{
		S[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &A[i]);
			S[i] = S[i - 1] + A[i];
		}
		memset (vis, 0, sizeof (vis));
		printf("%d\n", 2 * dp ( 1, n ) - S[n]);
	}
	return 0;
}

uva10891::uva10891(void)
{
}


uva10891::~uva10891(void)
{
}