题目链接:
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) { }