题解：P11325 【MX-S7-T3】「SMOI-R2」Monotonic Queue

赛时思路。

不难发现前一个区间的

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)

的。

赛时代码加注释：

CPP

#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

是否为空的判断，使代码更加简短。

CPP

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;

题解：P11325 【MX-S7-T3】「SMOI-R2」Monotonic Queue

文章操作

相关推荐

评论

题解：P11325 【MX-S7-T3】「SMOI-R2」Monotonic Queue