描述

有一个长度为n的整数序列，A和B轮流取数，A先取，每次可以从左端或者右端取一个数，所有数都被取完时游戏结束，然后统计每个人取走的所有数字之和作为得分，两人的策略都是使自己的得分尽可能高，并且都足够聪明，求A的得分减去B的得分的结果。

输入

输入包括多组数据，每组数据第一行为正整数n（1<=n<=1000）,第二行为给定的整数序列Ai（-1000<=Ai<=1000）。

输出

对于每组数据，输出A和B都采取最优策略的情况下，A的得分减去B的得分的结果。

样例输入

31 2 342 4 5 3

样例输出

20

来源

Yougth原创

上传者

TC_杨闯亮

转#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<math.h>#include<queue>#include<stdlib.h>#include<vector>using namespace std;int a[1009],sum[1009],dp[1009][1009];int main(){    int n,i,j,k;    while(scanf("%d",&n)!=EOF)    {        memset(dp,0,sizeof(dp));        sum[0]=0;        for(i=1;i<=n;i++){            scanf("%d",&a[i]);            sum[i]=sum[i-1]+a[i];        }        for(i=1;i<=n;i++){ //因为这个dp[i][j]用到的是dp[i+1][j]，所以要这样写，先更新了每个dp[i][j]对应的dp[i+1][j]            for(j=1,k=i;k<=n;k++,j++){ //这里我想了好久，                dp[j][k]=a[j]+(sum[k]-sum[j]-dp[j+1][k]);//这个是A取左边的那个数，A先取，然后B在j+1~k之间取，dp[j+1][k]，相当于是对于A先取的情况来说的，现在是在dp[j+1][k]中先取B，这样A的值就是(sum[k]-sum[j]-dp[j+1][k])                if((a[k]+(sum[k-1]-sum[j-1]-dp[j][k-1]))>dp[j][k])                    dp[j][k]=a[k]+(sum[k-1]-sum[j-1]-dp[j][k-1]);            }        }        printf("%d\n",dp[1][n]-(sum[n]-dp[1][n]));    }    return 0;}

　　

nyoj 1030