题解 UVA10891 【Game of Sum】

永不复行 · 2019-11-15 14:30:48 · 个人记录

第一道区间dp,平时都是线性扫的

(区间dp:再见了,我所爱的for循环...)

#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
#define dec(i,a,b) for(register int i=a;i>=b;i--)
using namespace std;
typedef long long LL;
inline void read(int &x)
{
    x=0;bool f=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=1;c=getchar();}
    while(c<='9'&&c>='0')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    if(f)x=-x;return;
}
inline void read(LL &x)
{
    x=0;bool f=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=1;c=getchar();}
    while(c<='9'&&c>='0')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    if(f)x=-x;return;   
}
const int mx=66049;
int n,a[110];
LL f[110][110],sum[110];
bool v[110][110];
LL dp(int l,int r)
{
    if(v[l][r])return f[l][r];
    v[l][r]=1;LL ret=0;
    inc(k,l,r-1)ret=min(ret,dp(l,k));
    inc(k,l+1,r)ret=min(ret,dp(k,r));
    f[l][r]=sum[r]-sum[l-1]-ret;
    return f[l][r];
}
int main()
{
    read(n);
    while(n!=0)
    {
        inc(i,1,n)read(a[i]);
        inc(i,1,n)sum[i]=sum[i-1]+a[i];
        LL Ans=dp(1,n);
        printf("%lld\n",(Ans<<1)-sum[n]);
        inc(i,1,n)inc(j,1,n)
            v[i][j]=false,f[i][j]=0;
        read(n);    
    }
    return 0;
}