28.uva 10891 Game of Sum 记忆化dp

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

那题的题解 请戳这里

。。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
int 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;
}