自动搬运

查看原文

来自洛谷，原作者为

	qjyzLfy 渐行、渐远，渐觉…

搬运于2025-08-24 21:24:32，当前版本为作者最后更新于2020-03-05 00:42:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

1. 作者很菜，于是他假定部分读者和他一样菜，因此写得既详尽又冗长。

2. 若无特殊强调，本题解中的“连续”一般是指位置上而非数值上的连续。

3. 输入格式中的 $V_i$ 和 $A_i$ 在文中分别记为 $val_i$ 和 $num_i$ 。

4. 本题解设置了多层标题，建议读者跳过已理解的部分。

分析

题意：有一个正整数数列，每次消去连续的一段合法的数字，得到这段数字长度对应的分数。数列不必全部消去，求最终得分的最大值。其中“合法”，是指数字可分为恰有一个数重合的前后两段（每一段长度可为 $1$ ），前一段以 $1$ 为公差递增，后一段以 $-1$ 为公差递减。

这样的题目应该是用区间动规。

由于消去一些数字必须先使之连续，也就是必须先消去这段数字中间的所有数字，计算部分消去某段区间的最大得分就不太可行，因为转移时难以判断两个数字在什么条件下连续。所以更可行的办法计算完全消去一段连续区间的最大得分，记为 $ans_{l,r}$ 。

最后为了得出部分消去整段数列的最大得分，可对数列进行划分，直到每一段区间要么全部都被消去，要么全部都未被消去为止。这显然是可行的。

动规转移

消去某段区间时，只有两种可能：一次性消去，或分步消去。

若分步，则必有最后一步。这是绝大多数动规的突破口。

最后一步是消去“连续”的一段数字，而这段数字初始时不一定连续，所以其空缺处的数字都已经被消去了。当然，这些空缺都构成连续区间，而且彼此独立。

所以可以枚举最后一步消去的数字，然后计算被这些数字隔离出的所有连续区间的 $ans$ 值之和，再加上消去数字的得分。其最大值就是当前计算的区间的 $ans$ 值。

计算答案

现在要由完全消去某区间的得分的最大值，得出部分消去某区间的得分的最大值。可以用一个简单的动规。

一段区间，在最优方案下，除非它被完全消去，否则就可以被找到一个未消去的点 （废话）。从这个点处（左边或右边）把区间分成两段，两段各自按最优解处理，就可以得到当前处理区间的最优解。所以只要枚举“断点”，就可以由小区间最优解得到大区间最优解了。

实现

在完全消去时（第一次动规）：

无疑，转移时枚举消去的数字要靠搜索。为避免一个点一个点地找数值上相邻的数字（那样又难写又慢），可以使用（假）指针标记相邻数字。

这是就会发现可消情况可以表示为两棵树。把数列中的数视为点，为了使能一同消去的点连通，只需使让一棵树中每个点连接数值比它大 $1$ 的点，让另一棵树中每个点连接数值比它小 $1$ 的点即可。当然，这两棵树应该是单向的（从左到右或从右到左）。

现在我们有两种选择。

1. 最高点作根。向左向右分别建一棵下降的树。使用时分别在两棵树上搜索。

2. 最右边的点作根。向左建一颗向上的（即上升的，下同）树和一颗向下的树。使用时先在向上的树上搜索，并在每个子节点处尝试转换到向下的树上继续搜索。（当然从左边来也行）

显然方案 $1$ 搜索的深度更小，因此似乎应该更快。但考虑具体操作就会发现，搜索时无法立即确定消去的数字的长度，因为左右两边相互独立。因此，也就无法确定最优解。所以选择方案 $2$ 。

• 建树

数据范围很小，不妨枚举。第一个比当前点数值大 $1$ （小 $1$ ）的点为向上（向下）的树中当前点的长子，第一个与当前点数值相同的点为当前点的兄弟（两棵树中兄弟的情况是一样的，可以共用）。

• 动规的转移

假设待处理区间为 $[l,r]$ ，简记为 $S$ ， $ans_{l,r}$ 表示处理相应区间的最大得分。

在 $S$ 内枚举根节点 $t$ 开始搜索，每搜索到一个点，判断当前得分（即最后一步要消去的数到此为止，后面的数不再被消去时的得分，下同）是否大于当前区间的得分。然后，如果是在向上的树上，就搜索其向上和向下的子节点，搜到向下的子节点时进入向下的树；如果是在向下的树上，就只搜索向下的子节点。直到子节点在 $l$ 左边为止。（子节点不存在时将搜到 $0$ ，而 $0<l$ 。）

其中，当前得分的计算方法是：用一个参数 $red$ 记录消去数列中间空缺区间的得分。从父节点 $f$ 进入子节点 $s$ 时， $red_{s}=red_{f}+ans_{s+1,f-1}$ 。再用一个参数 $len$ 记录搜索到当前节点时消去数字的长度，最后 $p$ 点的当前得分就是 $red_{p}+ans_{l,p-1}+val_{len}$ 。显然要把根节点 $t$ 处的 $red$ 初始化为 $ans_{t+1,r}$ 。

为方便处理中间的区间为空（即消去的数字原本就连续，或者消去的数字和端点 $l,r$ 连续）的情况，令 $ans_{i+1,i}=0$ 。

在部分消去时（第二次动规）：

这一步并不是复杂度的主要来源，可以无脑一些。下面用 $ans'_{l,r}$ 表示部分消去区间 $[l,r]$ 的最大得分。（读下一句话时请注意每个 $ans$ 右上角有没有 $'$ 。）

先把单个点的最大得分 $ans'$ 初始化，即 $ans'_{i,i}=max\{ans_{i,i},0\}$ ，然后计算 $ans'_{l,r}$ 时枚举断点 $t$ ，令 $ans'_{l,r}=max\{ans_{l,r},ans'_{l,t}+ans'_{t+1,r}\}$ 即可。

因为 $ans'$ 是在 $ans$ 的基础上与多个数比较取最大值得来的，可以直接用新最大值覆盖在原来的 $ans$ 上，不用定义新变量还省了初始化。

优化

优化当然是针对复杂度最大的第一次动规进行的，特别是针对其中的搜索进行的。

优化 1 ：剪枝

搜索到一个点时，如果可以确定，不管接下来的情况再怎么顺利，都不能得到更优解，就可以剪枝了。

而最理想的情况应该是接下来所有点都连续的情况。因为这时可以绝对自由地选择消去方法。所谓“自由”是因为决定得分的只是每次消去的区间的长度，而所有长度“分配”方式现在都可以做到。

但即使如此依然有很多选择，而现在需要直接找到最优的一种。

按照游戏的正常逻辑，直接把一个长为 $k$ 的合法区间消去，应该比把它拆分为两个短的区间再消去要优。否则，所有长为 $k$ 的合法区间都可以这样拆分，就永远不会有消去长为 $k$ 的区间的操作了。

但是出题人未必如此出题。不过，既然所有长度为 $k$ 的区间都可以这样拆分，就用拆分后的得分代替原得分好了。即 $val'_{k}=max\{val_{k},val'_{t}+val'_{k-t}\}$ 。这一步要对所有的 $k$ 由小到大处理一遍。

这样做相当于把所有消去区间连续的消去操作“合并”了，所以不影响正确性。

在此基础上，消去一段连续合法数字的最优方法一定是直接一步消去，最理想情况下的最大得分也就是直接一步消去的得分了。

具体来说，对于区间 $[l,r]$ ，搜索到 $t$ 点时。假如 $ans_{l,r} \ge red_{t}+val_{len+t-l}$ ，就可以剪枝了。

现在，可以搜到一个点时剪枝（就是上面的写法），也可以在将要搜索某个点之前就判断并剪枝。后面一种策略避免了进入下一级函数，因而更快。相应判别式略。

优化 2 ：省略

还记得搜索前需要枚举起点 $t$ 。而如果最后一次消去的区间右端点为 $t$ ，那么 $t$ 右边的连续段（不含 $t$ ）和左边的连续段（含 $t$ ）必然是各自独立地消去的。因为其它消去操作不可能跨过 $t$ 而消去其两边的数字。这时就可以直接用两段相加来代替搜索。即 $ans_{l,r}=max\{ans_{l,t}+ans_{t+1,r},ans_{t=r}\}$ 。

$t=r$ 时还是要搜索的。因为此时 $t$ 并没有把区间 $[l,r]$ 分成两段。

优化 3 ：再次剪枝

与“省略”类似地可以推出，唯一值得搜索的最后一步消去，不但一定要始于 $r$ ，而且一定要终于 $l$ 。

向上搜索到 $t$ 时，只有在 $num_t>num_l$ 时才转入向下的搜索。只有 $t=l$ 时才将当前得分与 $ans_{l,r}$ 进行比较。这时当前得分为 $red+val_{len}$ 。

向下搜索到 $t$ 时，如果 $num_t=num_l+1$ ，直接连向 $l$ 。这样则不会出现 $num_t \le num_l$ 的情况。

$O_{2}$ 优化

如题。

代码

#include <cstdio>
#include <algorithm>
#define LL long long
#define oo 0x3f7f7f7f
using namespace std;

const int nma=155;
int n,val[nma],num[nma];//输入 
int dso[nma],uso[nma],bo[nma];//树 
int ans[nma][nma];//意义同题解 
int i,j,l,r,d,t;


void dsea(int t,int len,int red){//向下搜索 
	if(num[t]==num[l]+1){//剪枝 2 
		ans[l][r]=max(ans[l][r],red+val[len+1]+ans[l+1][t-1]);
		return;
	}
	for(int ion=dso[t];ion>=l;ion=bo[ion]){
		if(red+ans[ion+1][t-1]+val[len+1+ion-l]>ans[l][r])//剪枝 1 
			dsea(ion,len+1,red+ans[ion+1][t-1]);
	}
	return;
}

void usea(int t,int len,int red){//向上搜索
	if(t==l)	ans[l][r]=max(ans[l][r],red+val[len]);
	for(int ion=uso[t];ion>=l;ion=bo[ion]){
		if(red+ans[ion+1][t-1]+val[len+1+ion-l]>ans[l][r])//剪枝 1
			usea(ion,len+1,red+ans[ion+1][t-1]);
	}
	if(num[t]>num[l]){//剪枝 2
		if(num[t]==num[l]+1){//剪枝 2
			ans[l][r]=max(ans[l][r],red+val[len+1]+ans[l+1][t-1]);
			return;
		}
		for(int ion=dso[t];ion>=l;ion=bo[ion]){
			if(red+ans[ion+1][t-1]+val[len+1+ion-l]>ans[l][r])
				dsea(ion,len+1,red+ans[ion+1][t-1]);
		}
	}
	return;
}

int main()
{
	//freopen("1.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			ans[i][j]=-oo;//第一次动规时ans有负值. 
	for(i=1;i<=n;i++){
		scanf("%d",&val[i]);
		for(t=1;(t<<1)<=i;t++)	val[i]=max(val[i],val[t]+val[i-t]);
		ans[i][i]=val[1];
		ans[i+1][i]=0;
	}
	ans[1][0]=0;
	for(i=1;i<=n;i++){
		scanf("%d",&num[i]);
		for(j=i-1;j;j--)
			if(num[j]==num[i])	{ bo[i]=j; break; }
		for(j=i-1;j;j--)
			if(num[j]+1==num[i])	{ dso[i]=j; break; }
		for(j=i-1;j;j--)
			if(num[j]==num[i]+1)	{ uso[i]=j; break; }
	}
	//以上为读入,ans初始化,建树. 
	
	for(d=1;d<n;d++){
		for(l=1,r=l+d;r<=n;l++,r++){
			for(t=l;t<r;t++){
				ans[l][r]=max(ans[l][r],ans[l][t]+ans[t+1][r]);
			}
			usea(r,1,0);
		}
	}
	//以上为第一次动规 
	
	for(i=1;i<=n;i++)
		if(ans[i][i]<0)	 ans[i][i]=0;
	for(d=1;d<n;d++){
		for(l=1,r=l+d;r<=n;l++,r++){
			for(t=l;t<r;t++){
				ans[l][r]=max(ans[l][r],ans[l][t]+ans[t+1][r]);
			}
		}
	}
	//以上为第二次动规 
	
	printf("%d",ans[1][n]);
	return 0;
}

后记

后记的前言

本后记为作者做本题的体会，供萌新为鉴，如果您觉得此题难度一般，则本后记对您应该没有任何帮助。如果您觉得此题难度只是有一点难，则建议您跳过“后记的正文”。

后记的正文

做本题之前，我接触过的区间动规仅限于由小区间推出其合并而成的大区间。因此刚做到本题时，我觉得因为子区间中消去一些数字后剩下的数不连续，根本无法表述，因此也无法动规。尝试搜索无果后我毫不犹豫得点开了题解。（这里我犯的错误很明显：从第一步而不是最后一步开始考虑。）

然而当时还没有题解，于是我只好自己想。一开始我依然是考虑第一步。而且居然还有结果。我当时想到的是，把消去的中间一段两端剩下的点叫断点，后续消去操作中，如果不把断点一同消去，则用消去了其中一个断点的操作扩大中间的消去段，否则利用断点被一同消去的这次操作扩大中间的消去段。直到中间消去段不可扩大为止。但是消去段不可扩大的条件被我想得太简单了。

但是这个过程启发我想到了把目标区间中间的区间拿出来，使拿出的部分和剩下的部分都可算。于是最后终于想到了没有任何优化的半正确算法。（70分）

第一个优化，是把最理想的情况单独看成一项任务，重新考虑而想到的；第二个优化，把某一次搜索的情况画成个图，看看就想到了；第三个优化自然也就跟着想到了。

实际上，本题在我的任务栏里停了一个月，而实际做题大概用了四天。

后记的后记

一些心得，美芹之献。

1. 有时候我们觉得完全没办法，其实是没有深入地思考，或者说没有思考的起点。这时候把目前能思考到的最后一步的情况详细描绘出来，从每一个最细微的局部去作考虑，有可能取得进展。

2. 区间动规中，合并小区间并不是得到大区间的唯一方法，但一般是最好的方法。

3. 常数优化的效果可能是惊人的。