这题和上次的通化邀请赛的那题一样，而且还是简化版本。。。

那题的题解      

。。。

 

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define INF 0x3f3f3f3fint dp[105][105];int a[105];int sum,n;int pre_sum[105],next_sum[105];int dfs(int b,int t,int sums){    if(dp[b][t]!=INF) return dp[b][t];    if(b+t==n) return 0;    int maxn=-INF;    for(int i=1;i+b+t<=n;i++)    {        maxn=max(maxn,sums-dfs(b+i,t,sum-pre_sum[b+i]-next_sum[n-t+1]));        maxn=max(maxn,sums-dfs(b,t+i,sum-pre_sum[b]-next_sum[n-t-i+1]));    }    return dp[b][t]=maxn;}int main(){    while(scanf("%d",&n)&&n)    {        sum=0;        next_sum[n+1]=pre_sum[0]=0;        for(int i=1;i<=n;i++)        {            scanf("%d",&a[i]);            sum+=a[i];            pre_sum[i]=pre_sum[i-1]+a[i];        }        for(int i=n;i>=1;i--)            next_sum[i]=next_sum[i+1]+a[i];                        memset(dp,0x3f,sizeof(dp));        dfs(0,0,sum);        printf("%d\n",dp[0][0]-(sum-dp[0][0]));    }    return 0;}