Sum游戏 Uva10891【区间dp】

题目大意

给定一个序列，A,B玩家轮流取数，每次只能从一段取若干个数，一个人取数的和代表该人的得分，若A,B都采取最优策略，问A的得分-B的得分

题目分析

对于都是正数的情况，肯定一次取完就可以。
但是由于有负数，所以我们就要考虑枚举取法

已知取完后的序列一定是原序列的一个子序列，因此，我们枚举取法
dp[i][j] 表示剩下 i,j 这个区间的序列的数时，先手能够取得的最大结果

dp[i][j] 应该 $sum(i,j)-min(0,dp[i\left]\right[k\left]\right(i\le k\&lt;j),dp[t\left]\right[j\left]\right(i+1\le t\le j)）$sum(i,j)−min(0,dp[i][k](i≤k<j),dp[t][j](i+1≤t≤j)）
sum(i,j) 表示 i,j的区间和
更新的时候采用区间dp的方式更新就可以了

代码详解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+50;
const int mod=1e9+7;
ll a[maxn];
int n;
ll sum[maxn];
ll dp[maxn][maxn];
ll getsum(int x,int y)
{
    return sum[y]-sum[x-1];
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
        for(int l=1;l<=n;l++)
        {
            for(int i=1;i+l-1<=n;i++)
            {
                int j=i+l-1;
                dp[i][j] = getsum(i,j);
                ll t = 0;
                for(int k=i+1;k<=j;k++) t = min(t,dp[k][j]);
                for(int k=i;k<j;k++) t=min(t,dp[i][k]);
                dp[i][j]=dp[i][j]-t;
               // cout<<i<<" "<<j<<" "<<t<<" "<<dp[i][j]<<endl;
            }
        }
        printf("%lld\n",dp[1][n]*2-sum[n]);
    }
    return 0;
}
/*
4
4 -10 -20 7
4
1 2 3 4
0


*/

而对于中间求最小值的过程，也可以在区间dp中进行优化
设 $f\left[i\right]\left[j\right]=min\left(dp\right[i\left]\right[k\left]\right)(i\le k\&lt;j)$f[i][j]=min(dp[i][k])(i≤k<j)
$g\left[i\right]\left[j\right]=min\left(dp\right[t\left]\right[j\left]\right)(i+1\le t\le j)$g[i][j]=min(dp[t][j])(i+1≤t≤j)

可写成
$f\left[i\right]\left[j\right]=min\left(dp\right[i\left]\right[j],f[i+1\left]\right[j\left]\right)$f[i][j]=min(dp[i][j],f[i+1][j])
$g\left[i\right]\left[j\right]=min\left(dp\right[i\left]\right[j],g[i\left]\right[j-1]$g[i][j]=min(dp[i][j],g[i][j−1]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+50;
const int mod=1e9+7;
ll a[maxn];
int n;
ll sum[maxn];
ll dp[maxn][maxn];
ll getsum(int x,int y)
{
    return sum[y]-sum[x-1];
}
ll f[maxn][maxn],g[maxn][maxn];
int main()
{
    while(scanf("%d",&n)&&n)
    {
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
        for(int l=1;l<=n;l++)
        {
            for(int i=1;i+l-1<=n;i++)
            {
                int j=i+l-1;
                dp[i][j] = getsum(i,j);
                ll t = 0;
                t = min(t,f[i+1][j]);
                t = min(t,g[i][j-1]);
                dp[i][j]=dp[i][j]-t;
                f[i][j] = min(dp[i][j],f[i+1][j]);
                g[i][j]=min(dp[i][j],g[i][j-1]);
               // cout<<i<<" "<<j<<" "<<t<<" "<<dp[i][j]<<endl;
            }
        }
        printf("%lld\n",dp[1][n]*2-sum[n]);
    }
    return 0;
}