UVA 10891 SUM游戏 DP

刚看到这个题目不知道怎么个DP法，有点难想到

解法如下

设置dp[i][j]代表i到j这段子序列能获得的最大值，这样，枚举m=min(m,dp[i+1到j][j],dp[i][i到j-1])，m就代表了给另一个人的,就可求得就只能取到 dp[i][j]-sum(i,j)-m,这样，sum为该段序列总和，只需简单的数列前缀和即可求得sum，这样，只需枚举m值，不断向下进行记忆化搜索，即可求得终结果。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int dp[110][110];
int vis[110][110];
int s[110];
int solve(int i,int j)
{
    if (vis[i][j]) return dp[i][j];
    vis[i][j]=1;
    int m=0;
    for (int k=i+1;k<=j;k++)
    {
        m=min(m,solve(k,j));
    }
    for (int k=i;k<j;k++)
    {
        m=min(m,solve(i,k));
    }
    dp[i][j]=s[j]-s[i-1]-m;
    return dp[i][j];
}
int main()
{
    while (scanf("%d",&n))
    {
        if (n==0) break;
        s[0]=0;
        int temp;
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&temp);
            s[i]=s[i-1]+temp;
        }
        memset(vis,0,sizeof vis);
        int ans=solve(1,n);
        ans=2*ans-s[n];//最后的结果是求A-B的值，A的值就为ans B的值为s[n]-ans;
        printf("%d
",ans);
    }
    return 0;
}