题解

#include<cstdio>
#include<queue>
using namespace std;
const int N = 300002;
int n, k, pre[N], dp[N];
struct node {
    int num, id;
    bool operator < (const node &t) const {
        if(num == t.num)
            return pre[id] < pre[t.id];
        return num > t.num;
    }
};
priority_queue <node> q;
int main() {
    char ch;
    scanf("%d %d", &n, &k);
    scanf("\n");
    for(int i = 1; i <= n; i ++) {
        ch = getchar();
        if(ch == 'G')
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = pre[i - 1] - 1;
    }
    q.push((node) {0, 0});
    for(int i = 1; i <= n; i ++) {
        while(q.top().id < i - k)//求的是前缀和，应为真实下标-1
            q.pop();
        dp[i] = (pre[i] >= pre[q.top().id]) ? q.top().num + 1 : q.top().num;
        q.push((node) {dp[i], i});
    }
    printf("%d\n", dp[n]);
    return 0;
}