题解：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) 的。

赛时代码加注释：

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