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

怎么大家都是 dp，来一个贪心（？）题解。

题意

有点复杂，自己看题面。

最终 sum 是所有通过右边弹出的元素的

c

的和。

思路

下文中，称 deque 的 front 为左边/前面。

观察题面中的代码，发现其实不需要管具体的

l_i,r_i

，而是可以理解为有若干次操作，每次让

r\gets r+1

或

l\gets l+1

，要求

l\leq r

，然后做单调栈的 push_back（可能带有 pop_back）或者 pop_front。

再做转化，变成选择一个

1\leq p \leq n

，指定一组不降的

a_{1\sim p}

，然后重复

p

次，每次令

r\gets r+1

，然后令

l\gets a_r

。这里的

l\gets l+1

和

r\gets r+1

同样也做单调栈操作。

先考虑如何算

a_i=1

的贡献。发现这样的话没有 pop_front 操作，直接做一遍单调栈即可，答案是每个前缀的

\max

。

然后观察 pop_front 操作起到了什么作用。发现它相当于每次 push 完后，删去单调栈的一个前缀（不能删空）。那么我们可以直接把这个操作放到 push 操作的弹栈过程中，每次从后面弹出时（除了每轮弹出的第一个元素，这是因为不能删空），你可以放弃这次弹出，改为直接把栈删空。

此后由于不存在 pop_front 操作，直接称 pop_back 为弹出。

之后我们可以开始贪了。每次弹出一个元素（设之为

x

）的时候，如果

c_x

非负，我们直接弹出它一定不亏。否则

c_x

是负的，此时如果我们只弹出

x

肯定时亏的，我们选择弹出它只可能因为在未来的某一时刻（不一定是这一次

r\gets r+1

导致的弹出）还要弹出此时的单调栈更左的元素，也就一定会弹出前一个元素（设之为

y

，如果不存在

y

那么弹

x

肯定亏）。那么我们可以直接令

c_y\gets c_y+c_x

，意思是如果需要弹出

y

，那么弹出

x

，否则不弹出

x

。在不弹出

y

的情况下，不弹出

x

和删空栈是等价的，所以这样写和原问题是等价的。

模拟这个过程即可。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c[500005],ans,a[500005],s;
deque<int>q;//用 stack 就行了 
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		int op=0;
		while(q.size()&&a[q.back()]<a[i]){
			int x=q.back();
			q.pop_back(); 
			if(op){
				if(c[x]>0) s+=c[x];//一定赚
				else if(q.size()) c[q.back()]+=c[x];//如果弹出 q.back()，那么弹出 x，否则清空。 
			}
			else s+=c[x],op=1;// 这是第一次弹出 
		}
		q.push_back(i);
		ans=max(ans,s);
	}
	cout<<ans;
}

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

文章操作

题意

思路

代码

相关推荐

评论

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