自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:06:27，当前版本为作者最后更新于2024-11-24 14:11:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛时思路。

不难发现前一个区间的 $l$ 可以且仅可以做到约束在做后一个区间时踢队尾最多踢到哪里（因为这是上一次踢队头踢到的位置），这样就可以通过上一个 $l$ 来控制当前踢队尾踢到最优处就停下。而对于第一个区间，程序必须从序列的最左端开始加数。下文中区间的左端点指的是踢队尾应该踢到哪里。

考虑 dp。设 $dp_{i,0/1}$ 表示最后一个区间右端点选到 $i$，这个区间的左端点有（$0$）或没有（$1$）要求必须是 $1$ 的时候（或者说，是否是第一个区间）的最大答案。

转移时模拟一个单调栈（或者说不踢队头的单调队列），每次从单调栈（队尾）踢出一个数之后就可以用区间左端点取到这里，右端点取到 $i$ 的答案拿来更新 $dp_{i,1}$。最后再用左边第一个大于 $a_i$ 的数的答案更新 $dp_{i,0/1}$。记得 $dp_{i,0}$ 只能从 $dp_{j,0}$ 转移，而 $dp_{i,1}$ 则可以从 $dp_{j,0}$ 和 $dp_{j,1}$ 转移。答案是所有 $dp_{i,1}$ 的最大值。代码里有具体的转移式，结合代码更好理解。

注意初始化的问题：$dp_{i,1}$ 刚开始必须从 $dp_{j,0}$ 转移过来才是有效的，所以没有从 $dp_{j,0}$ 转移而来的 $dp_{i,1}$ 刚开始应该设为无穷小。

因为转移过程是模拟一个单调栈，所以复杂度是 $O(n)$ 的。

赛时代码加注释：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int a[N],c[N],s[N];
int dp[N][2];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>c[i],s[i]=s[i-1]+c[i];
	for(int i=1;i<=n;i++)cin>>a[i];
	deque<int>q;//exactly a monotonic stack 
	for(int i=1;i<=n;i++){
		dp[i][1]=-1e18;
		while(!q.empty()&&a[q.back()]<a[i]){
			dp[i][1]=max(dp[i][1],s[i-1]-s[q.back()-1]+max(dp[q.back()][0],dp[q.back()][1]));
			//s[i-1]-s[q.back()-1]：从 i-1 踢到 q.back()，要把这里面的所有 c 加起来
			//max(dp[q.back()][0],dp[q.back()][1]))：左端点设到了 q.back()，这样才会踢到这里停下来；上一个右端点选择 q.back()，因为它不能小于 q.back()，而后面的点全部已经转移或者踢完了
			q.pop_back();
		}
		if(!q.empty())dp[i][1]=max(dp[i][1],s[i-1]-s[q.back()]+max(dp[q.back()][0],dp[q.back()][1]));
		if(!q.empty())dp[i][0]=s[i-1]-s[q.back()]+dp[q.back()][0];//中间踢的加起来，前面的转移过来
		else dp[i][0]=s[i-1];//一直踢到开头
		dp[i][1]=max(dp[i][1],dp[i][0]);//没有要求必须选最左边 ≠ 我不选最左边
		q.emplace_back(i);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i][1]);
	}
	cout<<ans;
	return 0;
}

上面是赛时的思路，而实际上本题的 dp 可以优化到不开两倍空间。

把 $dp_{i,0}$ 去掉。$dp_{i}$ 仍然需要初始化为无穷小，这样可以保证 $dp_i$ 在取最大值的时候只会从前面左端点到达 $1$ 的状态转移，因为刚开始有且只有 $dp_0=0$。这样，中间的主体代码就可以优化到更短。

另外，将 $a_0$ 改为 $n+1$ 并在一开始将 $0$ 放进 $q$ 中就可以避免对 $q$ 是否为空的判断，使代码更加简短。

a[0]=n+1;q.emplace_back(0);
int ans=0;
for(int i=1;i<=n;i++){
	dp[i]=-1e18;
	while(a[q.back()]<a[i]){
		dp[i]=max(dp[i],s[i-1]-s[q.back()-1]+dp[q.back()]);
		q.pop_back();
	}
	dp[i]=max(dp[i],s[i-1]-s[q.back()]+dp[q.back()]);
	q.emplace_back(i);
    ans=max(ans,dp[i]);
}
cout<<ans;