求助

DLDZD @ 2024-10-09 22:06:36

#include<bits/stdc++.h>
#define max(a,b) (a>b? a:b)
#define int long long
using namespace std;
int a[200001];
int dp[200001];
deque<pair<int,int> > q;
signed main(){
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++) cin>>a[i];
    int sum=0;
    for(int i=l;i<=n;i++){
        while(!q.empty()&&q.back().first<=dp[sum]) q.pop_back();
        q.push_back(make_pair(dp[sum],sum));
        while(q.front().second+r<i) q.pop_front();
        dp[i]=a[i]+q.front().first;
        sum++;
    }
    int num=-21474836450;
    for(int i=n-r+1;i<=n;i++) num=max(num,dp[i]);
    cout<<num;
    return 0;
}

by Elysialr @ 2024-10-09 22:22:41

#include<bits/stdc++.h>
#define max(a,b) (a>b? a:b)
#define int long long
using namespace std;
int a[200001];
int dp[200001];
deque<pair<int,int> > q;
signed main(){
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++){
        cin>>a[i];
        dp[i]=-(1<<30);
    } 
    int sum=0;
    q.push_back(make_pair(0,0));
    for(int i=l;i<=n;i++){
        while(!q.empty()&&q.back().first<dp[sum]) q.pop_back();
        q.push_back(make_pair(dp[sum],sum));
        while(!q.empty()&&q.front().second+r<i) q.pop_front();
        dp[i]=a[i]+q.front().first;
        sum++;
    }
    int num=-21474836450;
    for(int i=n-r+1;i<=n;i++)
    num=max(num,dp[i]);
    cout<<num;
    return 0;
}

by 114514xxx @ 2024-10-10 17:34:12

此贴终