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$个），即以下转移方程给出：

$$f[i] = a[i] + \min_{i - k - 1 \leq j < i} f[j]$$

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

$$\text{ans} = \text{sum}[n] - \min_{n - k \leq i \leq n} f[i]$$

代码

#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见祖宗。