洛谷 P1430 序列取数解题报告

P1430 序列取数

题目描述

给定一个长为(n)的整数序列((n<=1000))，由(A)和(B)轮流取数（(A)先取）。每个人可从序列的左端或右端取若干个数（至少一个），但不能两端都取。所有数都被取走后，两人分别统计所取数的和作为各自的得分。假设(A)和(B)都足够聪明，都使自己得分尽量高，求(A)的最终得分。

输入输出格式

输入格式：

第一行，一个正整数(T)，表示有(T)组数据。((T<=100))

接着(T)行，每行第一个数为(n)，接着(n)个整数表示给定的序列.

输出格式：

输出(T)行，每行一个整数，表示(A)的得分

看到足够聪明，我下意识以为是博弈论。。

但是似乎并不是，而且我想不出来怎么做。

对于取剩下的子序列([i,j]),先手有一个可求的最大得分值。

令(dp[i][j])为子序列([i,j])时，先手取可得的最大分数。

(dp[i][j]=max(sum[i][j],sum[i][j]-min{dp[i+k_1][j],dp[i][j-k_2],k_1in[1,j-i],k_2in[1,j-i]}))

分别对应先手者（于此步的）选全部，选左边的一段和选右边的一段三种情况。

我们发现这是三维的，需要枚举(k)。

优化？

拿(l[i][j])维护(min{dp[i+k_1][j],k_1in[1,j-i]})

拿(r[i][j])维护(min{dp[i][j-k_2],k_2in[1,j-i]})

当然，这两个东西的更新都是(O(1))的

细节：注意区间DP的枚举顺序性

code：

#include <cstdio>
#include <cstring>
const int N=1010;
int max(int x,int y) {return x>y?x:y;}
int min(int x,int y) {return x>y?y:x;}
int n,t;
int a[N],f[N],dp[N][N],l[N][N],r[N][N];
//l[i][j]=min{dp[i][j],dp[i+1][j]...dp[j][j]};
int read()
{
    int x=0,ff=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') ff=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return ff*x;
}

int main()
{
    t=read();
    for(int k=1;k<=t;k++)
    {
        n=read();
        memset(f,0,sizeof(f));
        memset(dp,0,sizeof(dp));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            f[i]=f[i-1]+a[i];
        }
        for(int i=1;i<=n;i++)
        {
            dp[i][i]=a[i];
            l[i][i]=a[i];
            r[i][i]=a[i];
        }
        for(int i=n-1;i>=1;i--)
            for(int j=i+1;j<=n;j++)
            {
                int sum=f[j]-f[i-1];
                dp[i][j]=max(sum,max(sum-l[i+1][j],sum-r[i][j-1]));
                l[i][j]=min(l[i+1][j],dp[i][j]);
                r[i][j]=min(r[i][j-1],dp[i][j]);
            }
        printf("%d
",dp[1][n]);
    }
    return 0;
}

2018.5.1