Uva 10891 - Game of Sum ( 区间dp )

时间:2022-09-01 15:40:45

题目链接:

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]表示开局者玩家Aij部分得到最大和,sum[i][j]表示从ij和,由于只能从两端取石子,要么有从最左端,要么从最右端。则有转移方程:

    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)
{
}