算法来了（讨论推动算法）
Program国度的人，喜欢玩这样一个游戏，在一块板上写着一行数，共n个。两个游戏者，轮流从最右或最左取一个数。刚开始，每个游戏者的得分均为零。如果一个游戏者取下一个数，则将该数的值加到该游戏者的得分上，最后谁的得分最高谁就赢了游戏。给出这n个数( 从左往
右), 假设游戏者都是非常聪明的，问最后两个人的得分(假设第一个人首先取数)．
【样例输入】
6
4 7 2 9 5 2
【样例输出】
18 11
【玩家1如果取1，玩家2就就可以取左边第一个7或右边2，然后玩家1两边也可以，依次类推】
先输出玩家1分数，空格打开，再输出玩家2
（好久没来论坛了，先放个题目！其实是别人叫我帮忙的题目，大家可能做过！水平有限，自己想了很久，但感觉算法还是有点烦！希望大家多讨论，让偶多学习！谢谢！）
搜索更多相关的解决方案:
算法
----------------解决方案--------------------------------------------------------
用动态规划吧..
----------------解决方案--------------------------------------------------------
三次方DP
[color=white]
----------------解决方案--------------------------------------------------------
燕子，来个程序吧？好久没学习你的算法了
学习学习！
----------------解决方案--------------------------------------------------------
也许这样可以
程序代码：
#include <iostream>
using namespace std;
inline int Max(int a,int b)
{
return a>b?a:b;
}
int a[1001];
int _sum[1001];
int dp[1001][1001];
inline int sum(int i,int j)
{
return _sum[j]-_sum[i-1];
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
_sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
_sum[i]=_sum[i-1]+a[i];
}
for(int i=n;i>=0;i--){
dp[i][i]=a[i];
for(int j=i+1;j<=n;j++){
dp[i][j]=Max(a[i]+sum(i+1,j)-dp[i+1][j],a[j]+sum(i,j-1)-dp[i][j-1]);
}
}
printf("%d %d\n",dp[1][n],sum(1,n)-dp[1][n]);
}
}
----------------解决方案--------------------------------------------------------
转移费用是1，所是是二次。。。又想当然了。。。
[color=white]
----------------解决方案--------------------------------------------------------
谢谢！LEECO！
------------------
dp[i][i+1] = a[i]与a[i+1]的大者
dp[m][n] = (a[m]+.....+a[n]-dp[m+1][n] 与 a[m]+.....+a[n]-dp[m][n-1]之间的大者）
但看不出来有没有考虑全面了？
----------------解决方案--------------------------------------------------------