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

考虑每一个区间设当前区间为

l_x,r_x

,其上一个区间为

l_y,r_y

,发现对于答案贡献仅同

r_x, l_y

有关

并且发现对于

i

要么从队头出去, 要么从第一个满足

(i < j)

并且

(a_i < a_j)

的

j

这里出去,定义

j

为

i

出点

dp_i

表示右端点为

i

的答案最大值,所以在

(i < j)

条件下

dp_j = dp_i + sum[i, j] (a_i < a_j)

(

j

为

i

出点)

dp_j = dp_i + sum[i + 1, j] (a_i < a_j)

(

j

不为

i

出点)

综上可以基于维护一个单调栈来维护出点,然后进行

dp

详情见代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 601000, INF = 2e12;
int dp[N], v[N], sum[N], a[N];
int stc[N], top, n, ans = -INF;
signed main () {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &v[i]), sum[i] = sum[i - 1] + v[i]; 
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), dp[i] = - INF; 
	for (int i = 1; i <= n; i++) {
		while (top && a[stc[top]] < a[i]) 
			dp[i] = max(dp[i], dp[stc[top]] + sum[i - 1] - sum[stc[top--] - 1]);
		dp[i] = max(dp[i], dp[stc[top]] + sum[i - 1] - sum[stc[top]]);
		stc[++top] = i;
		ans = max(ans, dp[i]);
	}
	cout << ans << '\n';
	return 0;
}

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

文章操作

相关推荐

评论

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