gyro永不抽风

ああああああああああああああああおおおおおおおおおおおおおおおお

P2034 选择数字 - 单调队列

题目

题目描述

给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数,但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。

输入格式

第一行两个整数n,k

以下n行,每行一个整数表示a[i]。

输出格式

输出一个值表示答案。

输入输出样例

输入 #1
5 2
1
2
3
4
5 
输出 #1
12

说明/提示

对于20%的数据,n <= 10

对于另外20%的数据, k = 1

对于60%的数据,n <= 1000

对于100%的数据,1 <= n <= 100000,1 <= k <= n,0 <= 数字大小 <= 1,000,000,000

时间限制500ms

题解

我们要选出和最大的一堆数,但是这非常难,所以我们可以考虑怎么做才能删除最少的数。设$f[i]$表示删除第$i$个数的最小和,那么$f[i]$可以由前$k+1$个$f$转移而来(因为是不超过$k$个),即以下转移方程给出:

观察后半段,其实就是个单调队列,直接维护就行了。最后的答案:

代码

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 <iostream>
#define int long long

using namespace std;

const int maxn = 100005;
int n, k, f[maxn], a[maxn];
struct node { int val, pos; } q[maxn];

signed main() {
cin >> n >> k;
f[0] = 0;
int head = 0, tail = 1, sum = 0;
// min -> increase
q[head] = (node) { f[0], 0 };
for (int i = 1; i <= n; i ++) {
cin >> a[i];
sum += a[i];
f[i] = a[i] + q[head].val;
while (head < tail && f[i] <= q[tail - 1].val) tail --;
q[tail ++] = (node) { f[i], i };
while (head < tail && i - q[head].pos + 1 > k + 1) head ++;
}
// for (int i = 0; i <= n; i ++) cout << f[i] << " ";
// cout << endl;
int ans = 8e18;
for (int i = n - k; i <= n; i ++) ans = min(ans, f[i]);
cout << sum - ans << endl;
return 0;
}

注意

十年OI一场空,不开longlong见祖宗。

__EOF__
-------------本文结束感谢您的阅读-------------

本文标题:P2034 选择数字 - 单调队列

文章作者:gyro永不抽风

发布时间:2020年09月20日 - 20:09

最后更新:2020年09月20日 - 21:09

原始链接:http://gyrojeff.moe/2020/09/20/P2034-%E9%80%89%E6%8B%A9%E6%95%B0%E5%AD%97-%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 转载请保留原文链接及作者!

真的不买杯奶茶吗?T^T

欢迎关注我的其它发布渠道