算法

(multiset优化dp) $O(n\log n)$

记 dp[i] 表示前 $i$ 块牧草地能够得到的最小可能数量
令 $c_{ij} = \begin{cases} 1, & s[i, i+1, \cdots, j-1] \text{中至少有一半的} G \\\ 0, &\text{其他} \end{cases}$

那么可以得到转移方程：

$ dp[j] = \min\limits_{\max(0, j-K) \leqslant i \leqslant j-1} (dp[i] + c_{ij}) $

记 pre[i] 表示前 $i$ 块牧草地中 $H$ 和 $G$ 的数量差
那么 $\displaystyle c_{ij} = \begin{cases} 0, & pre[i] < pre[j]\\\ 1, &pre[i] \geqslant pre[j] \end{cases}$
通过预处理 $pre[0], pre[1], \cdots, pre[N]$，我们可以 $O(1)$ 得到 $c_{ij}$

直接暴力dp的复杂度是 $O(NK)$。

注意到对于任意的 $i$ 和 $j$，都有 $0 \leqslant c_{ij} \leqslant 1$
记 $m = \min\limits_{\max(0, j-K) \leqslant i \leqslant j-1} (dp[i])$
于是，有 $ m \leqslant dp[j] \leqslant m + 1 $
那么问题就变成了判定是否能找到位于 $[\max(0, j-K), j-1]$ 之间的某个 $i$ 满足 $dp[j] + c_{ij} = m$

为了实现这一目的，我们可以通过维护以下两种功能的数据结构：

• 查询 $dp[i]$ 的最小值 $\to$ multiset
• 找到 $dp[i]$ 对应的最小的 $pre$ 值 $\to$ 用 map 来维护从 $dp[i]$ 到它对应的所有可能的 $pre$ 值的映射

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    vector<int> pre(n+1);
    rep(i, n) {
        if (s[i] == 'H') pre[i+1] = pre[i]+1;
        else pre[i+1] = pre[i]-1;
    }

    vector<int> dp(n+1);
    multiset<int> dpvals;
    multiset<int> mp[n+1];
    dp[0] = 0;
    dpvals.insert(0);
    mp[0].insert(0);

    for (int i = 1; i <= n; ++i) {
        int mn = *dpvals.begin();
        if (*mp[mn].begin() < pre[i]) dp[i] = mn;
        else dp[i] = mn+1;
        dpvals.insert(dp[i]);
        mp[dp[i]].insert(pre[i]);

        if (i >= k) {
            dpvals.erase(dpvals.find(dp[i-k]));
            mp[dp[i-k]].erase(mp[dp[i-k]].find(pre[i-k]));
        }
    }

    cout << dp[n] << '\n';

    return 0;
}