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_1\in[1,j-i],k_2\in[1,j-i]\})\)

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

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

优化？

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

拿\(r[i][j]\)维护\(min\{dp[i][j-k_2],k_2\in[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\n",dp[1][n]);

    }

    return 0;

}

---

2018.5.1