题解：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_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

详情见代码

#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;
}