题解 P1430【序列取数】

iwprc · 2019-07-30 00:35:59 · 题解

Part 1

• 翻了翻网上关于此题的题解，发现大都是基于多开两个数组来优化O(n^3)的DP,使其对每一个状态的转移复杂度由O(n)变为O(1),但是这种方法常数过大，且相对于我接下来提出的解法，代码过于复杂，为了防止某些毒瘤出题人卡常数，卡空间，我决定写这篇题解。
• 可以发现这是一个博弈类问题，由于所有数的和一定，那么如果想要自己的数和最大，肯定要选择后手的和最小的来转移（不过好像在后面的解题过程中没有太大用处）
• 几个约定：
  2. S(i,j)=\sum_{k=i}^ja[k]
• 下面我们以L(i,j)为例，由于a[i]必选，所以它的后继区间是[i+1,j],那么有4种转移方式
  1. 下一步自己选a[i+1],则L(i,j)=a[i]+L(i+1,j)
  2. 下一步自己选a[j],由于a[i]和a[j+1]不连续，所以不可能有一个人在一步内同时取，故此状态不合法
  3. 下一步对方选a[i+1],则L(i,j)=a[i]+S(i+1,j)-L(i+1,j)
  4. 下一步对方选a[j],则L(i,j)=a[i]+S(i+1,j)-R(i+1,j)
• 注意，由于3,4步已经是对方在操作，所以对方一定会选择最利于自己的决策，所以3,4要先取\min,再与1取\max
• 初始化L(i,i)=R(i,i)=a[i]

• 转移方程

  1.

  L(i,j)=a[i]+\max\begin{cases}L(i+1,j)\\S(i+1,j)+\min\begin{cases}-L(i+1,j)\\-R(i+1,j)\end{cases}\end{cases}

  2.

  R(i,j)=a[j]+\max\begin{cases}R(i,j-1)\\S(i,j-1)+\min\begin{cases}-L(i,j-1)\\-R(i,j-1)\end{cases}\end{cases}
• 输出\max\{L(1,n),R(1,n)\}

代码1：

#include<cstdio>
const int N=1002;
int  T,n,i,j,len,a[N],s[N],l[N][N],r[N][N];
int max(int x,int y){
    return x>y?x:y;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",a+i);
            s[i]=s[i-1]+a[i];
            l[i][i]=r[i][i]=a[i];
        }
        for(len=1;len<n;len++)
            for(i=1;i+len<=n;i++){
                j=i+len;
                l[i][j]=a[i]+max(l[i+1][j],s[j]-s[i]-max(l[i+1][j],r[i+1][j]));
                r[i][j]=a[j]+max(r[i][j-1],s[j-1]-s[i-1]-max(l[i][j-1],r[i][j-1]));
            }
        printf("%d\n",max(l[1][n],r[1][n]));
    }
}

Part 2

• 如果仅仅是这样，可能并没有任何优化，但是下面才是我们今天的重头戏——区间DP的滚动数组优化。有人可能会问，i,j都不是在每一层都+1，或-1，该如何用一维数组来存每一层的状态呢？细心的同学可能会发现，代码1中的len不就是满足这个条件吗？
• 下面我们重新设计状态
  2. S(i,j)=\sum_{k=i}^ja[k]
• 初始化L(i,0)=R(i,0)=a[i]

• 转移方程

  1.

  L(i,j)=a[i]+\max\begin{cases}L(i+1,j-1)\\S(i+1,i+j)+\min\begin{cases}-L(i+1,j-1)\\-R(i+1,j-1)\end{cases}\end{cases}

  2.

  R(i,j)=a[i+j]+\max\begin{cases}R(i,j-1)\\S(i,i+j-1)+\min\begin{cases}-L(i,j-1)\\-R(i,j-1)\end{cases}\end{cases}
• 输出\max\{L(1,n-1),R(1,n-1)\}

这时候代码可能长这样：

#include<cstdio>
const int N=1002;
int  T,n,i,j,len,a[N],s[N],l[N][N],r[N][N];
int max(int x,int y){
    return x>y?x:y;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",a+i);
            s[i]=s[i-1]+a[i];
            l[i][0]=r[i][0]=a[i];
        }
        for(j=1;j<n;j++)
            for(i=1;i+j<=n;i++){
                l[i][j]=a[i]+max(l[i+1][j-1],s[i+j]-s[i]-max(l[i+1][j-1],r[i+1][j-1]));
                r[i][j]=a[i+j]+max(r[i][j-1],s[i+j-1]-s[i-1]-max(l[i][j-1],r[i][j-1]));
            }
        printf("%d\n",max(l[1][n-1],r[1][n-1]));
    }
}

然后我们就可以把j这一维去掉了：

#include<cstdio>
const int N=1002;
int T,n,i,j,a[N],s[N],l[N],r[N];
int max(int x,int y){
    return x>y?x:y;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",a+i);
            s[i]=s[i-1]+a[i];
            l[i]=r[i]=a[i];
        }
        for(j=1;j<n;j++)
            for(i=1;i+j<=n;i++){
                r[i]=a[i+j]+max(r[i],s[i+j-1]-s[i-1]-max(l[i],r[i]));
                l[i]=a[i]+max(l[i+1],s[i+j]-s[i]-max(l[i+1],r[i+1]));
                //注意要先转移r[i]，再转移l[i],因为r[i]的转移需要l[i]前一维的值
            }
        printf("%d\n",max(l[1],r[1]));
    }
}

• 然后就很容易地成为了此题的最快代码，希望对大家有帮助