自动搬运

查看原文

来自洛谷，原作者为

	iwprc **

搬运于2025-08-24 21:25:00，当前版本为作者最后更新于2019-07-30 00:35:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1

• 翻了翻网上关于此题的题解，发现大都是基于多开两个数组来优化$O(n^3)$的DP,使其对每一个状态的转移复杂度由$O(n)$变为$O(1)$,但是这种方法常数过大，且相对于我接下来提出的解法，代码过于复杂，为了防止某些毒瘤出题人卡常数，卡空间，我决定写这篇题解。

• 可以发现这是一个博弈类问题，由于所有数的和一定，那么如果想要自己的数和最大，肯定要选择后手的和最小的来转移（不过好像在后面的解题过程中没有太大用处）

• 几个约定：

  1. $a[i]$表示第$i$个数
  2. $S(i,j)=\sum_{k=i}^ja[k]$
  3. $L(i,j)$表示此时的区间为$[i,j]$,且第$i$个数必须取
  4. $R(i,j)$表示此时的区间为$[i,j]$,且第$j$个数必须取

• 下面我们以$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]$

• 转移方程

  $ 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$不就是满足这个条件吗？

• 下面我们重新设计状态

  1. $a[i]$表示第$i$个数
  2. $S(i,j)=\sum_{k=i}^ja[k]$
  3. $L(i,j)$表示此时的区间为$[i,i+j]$,且第$i$个数必须取
  4. $R(i,j)$表示此时的区间为$[i,i+j]$,且第$i+j$个数必须取

• 初始化$L(i,0)=R(i,0)=a[i]$

• 转移方程

  $ 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]));
	}
}

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