数据疑似有点疯狂

FatFish2505 @ 2024-03-03 12:52:25

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5 + 10;
int n, L, R, a[MAXN], dp[MAXN], q[MAXN], head = 1, tail = 0;
int main(){
    cin >> n >> L >> R;
    for(int i=0; i<=n; i++){ scanf("%d", &a[i]); }
    for(int i=0; i<=n-R; i++){ dp[i] = -2147483648; }
    for(int i=n-R+1; i<=n; i++){ dp[i] = a[i]; }
    for(int i=n-L; i>=0; i--){
        q[++tail] = dp[i+L];
        if(i+R+1 <= n && dp[i+R+1] == q[head]){ head++; } // 把这一行的 dp 错写成 a ，竟然只WA了一个subtask????
        while(tail - head + 1 > 1 && q[tail] > q[tail-1]){
            q[--tail] = q[tail];
        }
        dp[i] = max(dp[i], a[i] + q[head]); 
    }
    cout << dp[0];
    return 0;
}

by return_TLE @ 2024-03-03 13:48:19

没过就行

by hutongzhou @ 2024-03-05 17:01:16

为什么这么写也能过？

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5 + 10;
int n, L, R, a[MAXN], dp[MAXN], q[MAXN], head = 1, tail = 0;
int main(){
    cin >> n >> L >> R;
    for(int i=0; i<=n; i++){ scanf("%d", &a[i]); }
    for(int i=0; i<=n-R; i++){ dp[i] = -2147483648; }
    for(int i=n-R+1; i<=n; i++){ dp[i] = a[i]; }
    for(int i=n-L; i>=0; i--){
        q[++tail] = dp[i+L];
        if(i+R+1 <= n && dp[i+R+1] == q[head]){ head++; }
        while(tail - head + 1 > 1 && q[tail] > q[tail-1]){  // 这里改成 while(tail - head + 1 > 1 && q[tail] > q[head])
            q[--tail] = q[tail];
        }
        dp[i] = max(dp[i], a[i] + q[head]); 
    }
    cout << dp[0];
    return 0;
}

ac 记录

by Twlight！ @ 2024-03-10 11:25:59

数据放海了属于是（

by shayebuhxiaomengxin @ 2024-07-04 10:12:50

确实，我写了个dp想看看写的对不对，对了再用队列优化，结果就一个红其他都对了