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

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

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
31
32
33
34
#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;
}

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