题解

好家伙，时间内存又击败了两位大佬

#include <bits/stdc++.h>
#define maxn 300010
using namespace std;
int sum[maxn], dp[maxn], n, m, q[maxn];

int get(){
	char c = getchar();
	for (; c != 'H' && c != 'G'; c = getchar());
	return c == 'H' ? 1 : -1;
}

int main(){
	cin>>n>>m;
	for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + get(), dp[i] = 1e9;
	int h = 1, t = 1;
	for (int i = 1; i <= n; ++i){
		while (h <= t && i - q[h] > m) ++h;
		if (h <= t) dp[i] = dp[q[h]] + (sum[i] <= sum[q[h]]);
		while (h <= t && (dp[i] < dp[q[t]] || dp[i] == dp[q[t]] && sum[i] <= sum[q[t]])) --t;
		q[++t] = i;
	}
	cout<<dp[n];
	return 0;
}