单调队列，sub1全错，sub2全对

Qianmo_su @ 2024-10-12 01:31:35

#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int N = 3e5+10,INF = 0x3f3f3f3f;
int a[N],f[N],n,l,r,ans=-INF;
deque<int> q;

signed main()
{
    cin >> n >> l >> r;
    for(int i=0;i<=n;i++) cin >> a[i];
    memset(f,-INF,sizeof(f));
    f[0] = 0;
    for(int i=l;i<=n;i++)
    {
        while(!q.empty() && f[q.back()]<=f[i]) q.pop_back();
        q.push_back(i-l);
        while(!q.empty() && q.front()+r<i) q.pop_front();
        f[i] = f[q.front()]+a[i];
        if(i+r>n) ans = max(ans,f[i]);
    }
    cout << ans;
    return 0;
}

by CaoSheng_zzz @ 2024-10-12 11:59:36

@Qianmo_su 不是哥们你凌晨一点发

by CaoSheng_zzz @ 2024-10-12 12:01:26

@Qianmo_su

const int maxn = 2e5 + 1 ;
std::multiset<int> q ;
int f[maxn << 1] ;
bool vis[maxn << 1] ;
int n , l , r , ans = -2e9 ;

signed main() {
    n = read() , l = read() , r = read() ;
    for(int i=0 ; i<=n ; i++) f[i] = read() ;
    q.insert(0) , vis[0] = true ;
    for(int i=l ; i<=n ; i++) {
        if((int)q.size() > 0) { f[i] += *q.rbegin() ; vis[i] = true ;}
        else f[i] = -1e9 ;
        if(i - r >= 0 && vis[i - r] == true) q.erase(q.find(f[i - r])) ;
        if(i - l + 1 >= 1 && vis[i - l + 1] == true) q.insert(f[i - l + 1]) ;
    }
    for(int i=n-r+1 ; i<=n ; i++) ans = max(ans , f[i]) ;
    return output(ans) , 0 ;
}

看看我的，感觉我两代码思路挺像的

by CaoSheng_zzz @ 2024-10-12 12:03:21

@Qianmo_su 不是哥们你单调下标干什么

by Qianmo_su @ 2024-10-12 13:09:38

@CaoSheng_zzz 解决了，我出队的下标写错了嘤嘤嘤

by Qianmo_su @ 2024-10-12 13:09:49

@CaoSheng_zzz 已关注