思路

首先我们思考朴素的 dp 方程。

定义状态

首先定义 $dp_i$，表示当前最后一个分区是以 $i$ 结尾时均势区和更赛牛较多区的和的最小值。

然后我们定义 $cnt_i$ 表示 $[1,i]$ 范围内更赛牛减荷斯坦牛的数量，所以 $[l,r]$ 范围内更赛牛减荷斯坦牛的数量就是 $cnt_r - cnt_{l-1}$，在读入时只需要碰到字符 G 加 $1$，碰到字符 H 减 $1$ 就可以了。

转移方程

我们假设倒数第二个区间是以 $j$ 结尾的，则最后一个区间的范围是 $[j+1,i]$。由于一个区间的长度大于 $1$ 小于 $k$，所以 $j$ 的范围是从 $i-k$ 到 $i-1$。枚举每一个 $j$，如果 $sum_i-sum_j\geqslant0$，也就是说 $[j+1,i]$ 这个区间是一个均势区或更赛牛较多区，$dp_i=dp_j+1$，否则这不是均势区或更赛牛较多区，$dp_i=dp_j$，最后对所有的 $j$ 转移来的情况区最小值，方程如下：

$$ dp_i=\min\limits_{j=i-k}^{i-1} \begin{cases}dp_j+1&sum_i-sum_j\geqslant0\dp_j&sum_i-sum_j <0\end{cases} $$

时间复杂度 $\mathcal{O}(nk)$。

优化

很显然，这样一定会 TLE。

我们从状态转移处下手。由于每次转移的范围 $k$ 是固定的，所以没必要一个一个枚举 $j$，而可以用单调队列维护这段转移区间。队列内部存放决策的下标 $j$。

设 $f$ 为当前队首的值， $b$ 为当前队尾的值，则转移分三步：

如果 $i - f > k$ 且队列不为空，说明它超过了长度限制，不能从这里转移来，从队首弹出。循环弹出所有过期的。

转移 $dp_i$ 时，从 $dp_f$ 转移来，这时是最优的。

循环从队尾弹出过期时间早且不够优秀的。

什么叫“不够优秀”？

第一种情况，如果 $dp_b > dp_i$，那么从 $dp_b$ 转移不如 $dp_i$，弹出；第二种情况，如果 $dp_b = dp_i$，但是 $sum_i - sum_j \geqslant 0$，转移时需要加上 $1$，这样最多和 $dp_i$ 转移答案相同，或不及 $dp_i$，且比 $dp_i$ 过期得早，弹出。

核心代码如下：

1
2
3
4
5
6
while(!q.empty()&&i-q.front()>k)q.pop_front();
		int j=q.front();
		if(cnt[i]-cnt[j]>=0)dp[i]=dp[j]+1;
		else dp[i]=dp[j];
		while(!q.empty()&&(dp[q.back()]>dp[i]||(dp[q.back()]==dp[i]&&cnt[i]-cnt[q.back()]>=0)))q.pop_back();
		q.push_back(i);

时间复杂度 $\mathcal{O}(n)$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
char s[3*114514];
int cnt[3*114514],dp[3*114514];
deque<int>q;
int main(){
	int n,k;
	cin>>n>>k;
	scanf("%s",s+1);
	q.push_back(0);
	for(int i=1;i<=n;i++){
		if(s[i]=='G')cnt[i]=cnt[i-1]+1;
		else cnt[i]=cnt[i-1]-1;
		while(!q.empty()&&i-q.front()>k)q.pop_front();
		int j=q.front();
		if(cnt[i]-cnt[j]>=0)dp[i]=dp[j]+1;
		else dp[i]=dp[j];
		while(!q.empty()&&(dp[q.back()]>dp[i]||(dp[q.back()]==dp[i]&&cnt[i]-cnt[q.back()]>=0)))q.pop_back();
		q.push_back(i);
	}
	cout<<dp[n]<<endl;
	return 0;
}