Program国度的人，喜欢玩这样一个游戏，在一块板上写着一行数，共n个。两个游戏者，轮流从最右或最左取一个数。刚开始，每个游戏者

的得分均为零。如果一个游戏者取下一个数，则将该数的值加到该游戏者的得分上，最后谁的得分最高谁就赢了游戏。给出这n个数( 从左往

右), 假设游戏者都是非常聪明的，问最后两个人的得分(假设第一个人首先取数)．
【样例输入】
6
4 7 2 9 5 2
【样例输出】
18 11
【玩家1如果取1，玩家2就就可以取左边第一个7或右边2，然后玩家1两边也可以，依次类推】
先输出玩家1分数，空格打开，再输出玩家2

（好久没来论坛了，先放个题目！其实是别人叫我帮忙的题目，大家可能做过！水平有限，自己想了很久，但感觉算法还是有点烦！希望大家多讨论，让偶多学习！谢谢！）

用动态规划吧..

三次方DP


" border="0" />[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，所是是二次。。。又想当然了。。。



" border="0" />[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]之间的大者）

但看不出来有没有考虑全面了？