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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}

------ 本文结束 ------