80pts，11,12RE求调（双号壶关）

YCW13983841648 @ 2024-12-04 19:13:29

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
int l,r;
int a[N];
int dp[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>l>>r;
    for(int i=1;i<=n+1;i++){
        cin>>a[i-1];
        dp[i]=INT_MIN+1e3+10;
    }
    for(int i=0;i<=n;i++){
        for(int j=i+l;j<=i+r;j++){
            dp[min(j,n+1)]=max(dp[min(j,n+1)],dp[i]+a[j]);
        }
    }
    cout<<dp[n+1];
    return 0;
}

by KarmaticEnding @ 2024-12-04 19:23:41

@YCW13983841648

有没有一种可能：在您的双重循环 dp 里，j 最大可能到达 i+r，i 和 r 最大可能到达 n，所以 i+r 可能到达 2n，而 n 是 2\times 10^5，那么 2n 就是 4\times 10^5。

所以，您访问 \texttt{a[j]} 的时候，若 \texttt{j=2n=400000}，那么就访问越界了。

by YCW13983841648 @ 2024-12-04 19:25:49

@KarmaticEnding请您看看我在二重循环dq数组下标上的min

by KarmaticEnding @ 2024-12-04 19:26:31

@YCW13983841648

这样就过了

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=5e5+10;
int l,r;
int a[N];
int dp[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>l>>r;
    for(int i=1;i<=n+1;i++){
        cin>>a[i-1];
        dp[i]=INT_MIN+1e3+10;
    }
    for(int i=0;i<=n;i++){
        for(int j=i+l;j<=i+r;j++){
            dp[min(j,n+1)]=max(dp[min(j,n+1)],dp[i]+a[j]);
        }
    }
    cout<<dp[n+1];
    return 0;
}

虽然我是真的很不理解为什么 n=2\times 10^5 的情况下 O(n^2) 怎么过的

by YCW13983841648 @ 2024-12-04 19:26:36

@KarmaticEnding哦，我知道了，是a数组

by KarmaticEnding @ 2024-12-04 19:27:14

@YCW13983841648

我指的不是 dp 数组，而是 a 数组

by YCW13983841648 @ 2024-12-04 19:29:12

@KarmaticEnding已过已关