Codeforces 940E(DP+单调队列)

Codeforces 940E
题意：给你一个长为$n$的序列和一个数字$c$，你要将这个序列切成若干段，对于每一段，这段中最小的$\frac nc$个数字（向下取整）都会被自动删除，问怎么切割使最后剩下的数字和最小

可以证明一段长度不会超过$c$。假设有一段长度超过$c$，因为超过$c$的部分不能给这个段提供更大的删除值，而如果长度为$xc$($x$为任意正整数)，那么这个段可以分成$x$段$c$长度的段，并且答案可能更优。那么每一段长度等于$c$的段就只用删除一个数。
所以我们设$dp(i)$为前$i$个数删除数值的最大值，那么$dp(i)=dp(i-c)+min(a_j|i - c + 1 \leq j \leq i)$，删区间$[i-c+1, i]$最小的数。也有可能$i$点不取最优(在此处后面断开)，则$dp(i)=dp(i-1)$。

知识点：本题 DP 状态使用了补集转化思想，并且利用$dp(i)=dp(i-1)$来处理段长不为$c$的情况。

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, c, ai[100000 + 5], dp[100000 + 5], que[100000 + 5], l, r, sum = 0;
void clean() {}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) cin >> ai[i], sum += ai[i];
    dp[0] = 0;
    l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && que[l] < i - c + 1) l++;
        while (l <= r && ai[que[r]] >= ai[i]) r--;
        que[++r] = i;
        dp[i] = dp[i - 1];
        if (i - c >= 0) dp[i] = max(dp[i], dp[i - c] + ai[que[l]]);
    }
    cout << sum - dp[n];
    return 0;
}
int main() {
    cin >> n >> c, solve();
    return 0;
}