自动搬运

查看原文

来自洛谷，原作者为

	梧桐灯 梧桐灯下是我熄灯的双眼

搬运于2025-08-24 22:08:11，当前版本为作者最后更新于2019-09-21 10:20:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里用单调队列实现，吊打堆，时间复杂度只需O(n)

首先看到此题想到DP。容易得出下面的式子：

记$sum[i]$为$1$ ~ $i$ 中$H$的个数减去$G$的个数

$$f[i] = min \left\{f[j] + (sum[i] - sum[j] <= 0)\right\} $$$$(i - j <= k)$$

由于枚举j肯定要超时，我们想到用数据结构来维护DP

如果没有$(sum[i] - sum[j] <= 0)$这个东西，我们很容易想到用单调队列来维护，但加上后面这个呢？由于它不是1就是0，而且$sum[i]$值固定，那我们可以分类讨论：

对于$\forall p, q$ ($p, q$满足转移条件)：

若$f[p] \neq f[q]$，则我们肯定把小的放队首，因为即使它要加1也一定不会劣于另一个

若$f[p] = f[q]$, 则我们把$sum$小的放队首，这样拿$sum[i]$减后才更可能不小于0

有了以上推论&细节~~&卡常~~，你就不仅能AC，RP好还能进入最优解第一面（女装有益减小常数QwQ）

以下是代码（131ms）

#pragma GCC optimize ("Ofast")
#include <cstdio>
using namespace std;

inline void read (int& s) {
	s = 0;
	static char c = getchar ();
	while (c < '0' || c > '9') c = getchar ();
	while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c & 15), c = getchar ();
	return ;
}

const int N = 300007;
int n, k, f[N], sum[N];
int Q[N], H, T;

int main () {
	read (n), read (k);
	register int i; for (i = 1; i <= n; ++i) sum[i] = sum[i - 1] + (getchar () == 'H' ? 1 : -1);
	Q[T++] = 0; //刚开始前0头牛答案为0
	for (i = 1; i <= n; ++i) {
		while (H < T && i - Q[H] > k) ++H; //单调队列的出队操作
		f[i] = f[Q[H]] + (sum[i] - sum[Q[H]] <= 0);
		while (H < T) {
			if (f[i] < f[Q[T - 1]] || (f[i] == f[Q[T - 1]] && sum[i] < sum[Q[T - 1]])) --T;
			else break;
		} //入队操作，注意一下细节
		Q[T++] = i;
	}
	printf ("%d\n", f[n]);
	return 0;
}

个人觉得单调队列好写，好记，好快，为什么还用堆来维护呢