Bzoj 2442(区间DP+单调队列)

BZOJ 2442
设$dp(i)$为$i$不选，之前的选择合法时损失的最小效率
则$dp(i)=min(dp(j))+e_i$
而这是$O(n^2)$的，我们发现$min(dp(j))$满足单调性，且是一段区间的最小值，所以可以用单调队列来优化

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, k;
LL tot, ei[MAXN], dp[MAXN], que[MAXN * 2];
void clean() {
    tot = 0;
    ms(dp, 0), ms(que, 0);
}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%lld", &ei[i]), tot += ei[i];
    int l = 1, r = 1;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && que[l] < i - k - 1) l++;//单调队列左边是之前的 
        dp[i] = dp[que[l]] + ei[i];
        while (l <= r && dp[que[r]] >= dp[i]) r--;//单调队列右边是之后的 
        que[++r] = i;
    }
    LL mn = 1000000000000000000;
    for (int i = n - k; i <= n; i++) mn = min(mn, dp[i]);
    printf("%lld\n", tot - mn);
}
int main() {
    scanf("%d%d", &n, &k), solve();
    return 0;
}