顺推单调队列 dp 求调
查看原帖
顺推单调队列 dp 求调
347089
STA_Morlin楼主2024/7/7 20:55
#include <bits/stdc++.h>
namespace {
#define filein(x) freopen(x".in", "r", stdin)
#define fileout(x) freopen(x".out", "w", stdout)
#define files(x) filein(x), fileout(x)
using namespace std;
#define ll long long
#define db double

const int man = 1e5+10;
}

int n, m;
ll sum[man], f[man][2];
int a[man];
deque <int> dq;
int main () {
#ifndef ONLINE_JUDGE
    files("test");
#endif
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", a+i), sum[i] = sum[i-1]+a[i];
    dq.push_back(0);
    for (int i = 1; i <= n; ++ i) {
        while (dq.size() && i-dq.front()>m) dq.pop_front();
        f[i][0] = max(f[i-1][0], f[i-1][1]);
        f[i][1] = f[dq.front()][0]-sum[dq.front()]+sum[i];
        while (dq.size() && f[i][0]-sum[i]>f[dq.front()][0]-sum[dq.front()]) dq.pop_back();
        dq.push_back(i);
    } printf("%lld", max(f[n][0], f[n][1]));
    return 0;
}

// ---

目前的小 hack 数据能过。

2024/7/7 20:55
加载中...