题目描述 Description
小毛终于到达宝藏点，他意外地发现有一个外星人（名叫Pluto）。宝藏是一些太空黄金，有n堆排成一行，每堆中有xi颗黄金。小毛和Pluto决定轮流从中取出黄金，规则是每次只能从最左边或最右边取出一堆黄金，直到所有黄金被取出。小毛先取，两人都以最优策略进行选取，求两人的最后所得。
输入描述 Input Description
第一行是正数n(≤500)；第二行为n个正整数xi(≤300)，表示每堆黄金的个数。
输出描述 Output Description
仅两个整数，分别表示小毛和Pluto的得分，以空格隔开。
样例输入 Sample Input
6
4 7 2 9 5 2
样例输出 Sample Output
18 11
题解：
设dp[i][j]表示当取到只剩下i~j的元素时的先手的最优得分，这个转移非常好像，但第一次写类似博弈的题目，写详细一些。
首先我们有两种决策，对于区间i~j，可以取a[i],也可以取a[j],当我们取a[i]时，对手就还剩下区间i+1~j，那么此时他就变成了先手，按照最优策略取了dp[i+1][j],如果取a[j],那么还剩下区间i~j-1，那么他就会取dp[i][j-1],因为我们两个人的所取的总和是不变的，都是区间和，那么我们只有最小化他的取值，才能得到我们想要的最大得分。所以dp[i][i+len]=sum[i+len]-sum[i-1]-min(dp[i+1][i+len],dp[i][i+len-1])，因为我们是在保证后手也是用最优策略的情况下做出的判断，而转移也是用最优的转移，所以符合题意。
代码：
#include<iostream> #include<stdio.h> #include<cstring> #include<stdlib.h> #include<algorithm> #define MANX 1000 using namespace std; int dp[MANX][MANX],a[MANX],sum[MANX]; int n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; for(int i=1;i<=n;i++) dp[i][i]=a[i]; for(int len=1;len<=n-1;len++) for(int i=1;i+len<=n;i++) dp[i][i+len]=sum[i+len]-sum[i-1]-min(dp[i+1][i+len],dp[i][i+len-1]); printf("%d %d ",dp[1][n],sum[n]-dp[1][n]); }