uva 10891 - Game of Sum

题意：

   A,B两人依次从数组两边拿数字，每次任选一边拿走1+个，A先手，问最后A比B大多少

设代表i,j子序列先手可以取得的最大差值

转移方程为

有个状态，个转移，总复杂度为结果为f(1,n)

也可设f(i,j)为子序列和，则结果为2f(1,n)-sum(n)

转移方程为 f(i,j)=sum(i,j)-min{d(i+1,j)................}

利用i.j差值递增做转移可以将复杂度降为n^2

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 1000000000
bool vis[101][101];
int ans[101][101];
int n;
int sum[101];
int calc(int i,int j)
{
    if(i>j)return 0;
    if(vis[i][j])return ans[i][j];
    vis[i][j]=1;
    int t;
    int &tans=ans[i][j];
    tans=-inf;
    for(t=i+1;t<=j+1;t++)
    {
        tans=max(tans,sum[t-1]-sum[i-1]-calc(t,j));
    }
    for(t=j-1;t>=i;t--)
    {
        tans=max(tans,sum[j]-sum[t]-calc(i,t));
    }
    return tans;
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        int i;
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&sum[i]);
            sum[i]+=sum[i-1];
        }
        memset(vis,0,sizeof(vis));
        printf("%d\n",calc(1,n));
    }
}