题解 P1430 【序列取数】

· · 题解

题目大意：

一列数，两个都很聪明的人可以从任意一端取任意多个数，只能从一端取至少一个数，得分为取得的数的和，求A的得分。

思路

显而易见的是，无论怎么取，剩下的数列都是一段原数列的连续子序列

所以我们用d[i][j]表示第i~j个数组成的子序列，先手能取得的最大值

状态转移时，我们要枚举从左还是右取，以及取多少个，即对于断点k，剩下一个(k,j)或是(i,k)的子序列(i<=k<=j)

再用sum[i][j]表示i~j的和，则有

d[i][j]=sum[i][j]-min(d[i+1][j],d[i+2][j],...,d[j][j],d[i][j-2],d[i][j-1],d[i][i],0);其中 0 表示全取完。

最终答案也就为d[1][n]了

但这样是n^3的，所以我们需要一点优化。

定义`f[i][j]=min(d[i][j],d[i+1][j],d[i+2][j],...,d[j][j])

g[i][j]=min(d[i][j],d[i][j-1],d[i][j-2],...,d[i][i])`

那么转移方程变为:d[i][j]=sum(i,j)-min(f[i+1][j],g[i][j-1],0);

f,g也可以在O(1)时间内递推得到：

`f[i][j]=min(d[i][j],f[i+1][j]);

g[i][j]=min(d[i][j],g[i][j-1]);`

这样时间复杂度就将为了n^2，就可以过这道题了。

代码里还有一些小注释，再有安利洛谷博客https://www.luogu.org/blog/khassar/

//2017-12-21 21:23:24 星期四 by-z255491575
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>

#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memset((a),(b),sizeof((b)))
#define D double

using namespace std;

const int N=1005,inf=1e9;

int T,n,a[N],f[N][N],s[N],g[N][N],d[N][N];

IL int read() {
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
    return x*f;
}
IL void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

signed main()
{
    T=read();
    while(T--) {
        n=read();
        Rf(i,1,n) {
            a[i]=read();
            s[i]=s[i-1]+a[i];//前缀和——sum
        }
        Rf(i,1,n) f[i][i]=g[i][i]=d[i][i]=a[i];//初始化边界
        Rf(L,1,n) {//枚举长度
            Rf(i,1,n-L) {
                R int j=i+L,m=0;
                //递推部分
                m=min(m,min(f[i+1][j],g[i][j-1]));
                d[i][j]=s[j]-s[i-1]-m;
                f[i][j]=min(d[i][j],f[i+1][j]);
                g[i][j]=min(d[i][j],g[i][j-1]);
            }
        }
        write(d[1][n]);
        putchar('\n');
    }

    return 0;
}