代码

#include <iostream>

using namespace std;

const int maxn = 1005;

int a, b, n;
struct node { int val, pos; } q[maxn];
int map[maxn][maxn];
int min_val[maxn][maxn], max_val[maxn][maxn];
int min_ans[maxn][maxn], max_ans[maxn][maxn];

int main() {
	cin >> a >> b >> n;
	for (int i = 1; i <= a; i ++)
		for (int j = 1; j <= b; j ++)
			cin >> map[i][j];
	int head = 0, tail = 0;
	// row max
	for (int i = 1; i <= a; i ++) {
		head = 0, tail = 0;
		for (int j = 1; j <= b; j ++) {
			while (head < tail && map[i][j] >= q[tail - 1].val) tail --;
			q[tail ++] = (node) { map[i][j], j };
			while (head < tail && j - q[head].pos + 1 > n) head ++;
			if (j >= n) max_val[i][j - n + 1] = q[head].val; 
		}
	}
	// row min
	for (int i = 1; i <= a; i ++) {
		head = 0, tail = 0;
		for (int j = 1; j <= b; j ++) {
			while (head < tail && map[i][j] <= q[tail - 1].val) tail --;
			q[tail ++] = (node) { map[i][j], j };
			while (head < tail && j - q[head].pos + 1 > n) head ++;
			if (j >= n) min_val[i][j - n + 1] = q[head].val; 
		}
	}

	for (int j = 1; j <= b - n + 1; j ++) {
		head = 0, tail = 0;
		for (int i = 1; i <= a; i ++) {
			while (head < tail && max_val[i][j] >= q[tail - 1].val) tail --;
			q[tail ++] = (node) { max_val[i][j], i };
			while (head < tail && i - q[head].pos + 1 > n) head ++;
			if (i >= n) max_ans[i - n + 1][j] = q[head].val;
		}
	}
	for (int j = 1; j <= b - n + 1; j ++) {
		head = 0, tail = 0;
		for (int i = 1; i <= a; i ++) {
			while (head < tail && min_val[i][j] <= q[tail - 1].val) tail --;
			q[tail ++] = (node) { min_val[i][j], i };
			while (head < tail && i - q[head].pos + 1 > n) head ++;
			if (i >= n) min_ans[i - n + 1][j] = q[head].val;
		}
	}
	
	int ans = 2e9;
	for (int i = 1; i <= a - n + 1; i ++)
		for (int j = 1; j <= b - n + 1; j ++)
			ans = min(ans, max_ans[i][j] - min_ans[i][j]);
	
	cout << ans << endl;
	
	return 0;
}

P2034 选择数字 - 单调队列

发表于 2020-09-20 分类于 OI Disqus：
本文字数： 1.3k 阅读时长 ≈ 1 分钟
博客园同步已开启

题目

题目描述

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

输入格式

第一行两个整数n，k

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

输出格式

输出一个值表示答案。

输入输出样例

输入 #1

输出 #1

说明/提示

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

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

代码

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