CF 940E Cashback

题目描述

https://codeforces.com/problemset/problem/940/E

Solution

注意到我们一定能将最优解的划分变成只有 $1$ 和 $c$ 两种

时间复杂度 $O(n)$

#include <iostream>
#include <cstdio>
#define maxn 100010
#define ll long long
using namespace std;

int n, m, a[maxn], b[maxn];

int Q[maxn], h = 1, t = 0; 

ll f[maxn], s[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i]; 
    for (int i = 1; i < m; ++i) {
        while (h <= t && a[i] <= a[Q[t]]) --t;
        Q[++t] = i; 
    } 
    for (int i = m; i <= n; ++i) {
        while (h <= t && a[i] <= a[Q[t]]) --t;
        Q[++t] = i;
        while (h < t && i - Q[h] + 1 > m) ++h;
        b[i] = a[Q[h]];
    }
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + a[i];
        if (i - m >= 0) f[i] = min(f[i], f[i - m] + s[i] - s[i - m] - b[i]); 
    } cout << f[n] << "\n"; 
    return 0;
}