单调队列优化dp

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int dp[200005];
int a[200005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    deque<int> que;
    que.emplace_back(0);
    for (int i = 1 ; i <= n ; i++) {
        int idx = 0;
        while (!que.empty() && que.front() < i - m) {
            que.pop_front();
        }
        if (!que.empty()) {
            idx = que.front();
        }
        dp[i] = dp[idx] + a[i];
        while (!que.empty() && dp[que.back()] >= dp[i]) {
            que.pop_back();
        }
        que.emplace_back(i);
    }
    int ans = 0x7fffffff;
    for (int i = n - m + 1 ; i <= n ; i++) {
        ans = min(ans, dp[i]);
    }
    cout << ans << "\n";
    return 0;
}