Description

You have probably heard of the game “Rock, Paper, Scissors”. The cows like to play a similar game they call “Hoof, Paper, Scissors”.

你可能玩过石头剪刀布这个游戏, 奶牛们也喜欢玩类似的游戏, 叫做 “蹄子剪刀布”.

The rules of “Hoof, Paper, Scissors” are simple. Two cows play against each-other. They both count to three and then each simultaneously makes a gesture that represents either a hoof, a piece of paper, or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors beats paper (since scissors can cut paper), and paper beats hoof (since the hoof can get a papercut). For example, if the first cow makes a “hoof” gesture and the second a “paper” gesture, then the second cow wins. Of course, it is also possible to tie, if both cows make the same gesture.

蹄子剪刀布的规则和石头剪刀布的规则是一样的, 蹄子踩碎剪刀, 剪刀剪布, 布包蹄子.

Farmer John wants to play against his prize cow, Bessie, at \(n\) games of “Hoof, Paper, Scissors”\((1 \leq n \leq 100000)\). Bessie, being an expert at the game, can predict each of Farmer John ‘s gestures before he makes it. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same gesture multiple times in a row. In fact, she is only willing to switch gestures at most \(k\) times over the entire set of games \((0 \leq k \leq 20)\). For example, if \(k = 2\), she might play “hoof” for the first few games, then switch to “paper” for a while, then finish the remaining games playing “hoof”.

现在农夫约翰想要和他的最机智的奶牛 Bessie 玩蹄子剪刀布 (我也不知道 FJ 为什么有 蹄子), 一共进行了 \(n\) 轮 \((n \leq 10^5)\), Bessie, 作为一个奶牛, 非常的怠惰, 无论 她出什么, 都喜欢连续的出, 最多变化 \(k\) 次 \((k \leq 20)\), 也就是说, 对于她所出的, 记为序列 \(f(i)\), 记 \(sum\) 为有多少个 \(i\) 满足 \(f(i) \neq f(i-1) (i \gt 1)\), 而她的 \(sum\) 一定不会超过 \(k\).

Given the sequence of gestures Farmer John will be playing, please determine the maximum number of games that Bessie can win.

现在农夫约翰已经给出了他出的东西, 你要告诉 Bessie, 在不确定她出的东西的情况下, 她最多能赢多少次.

Input

The first line of the input file contains \(n\) and \(k\).

输入数据第一行为 \(n, k\).

The remaining \(n\) lines contains Farmer John’ s gestures, each either H,P, or S.

接下来 \(n\) 行表示农夫约翰所出的东西,H 表示蹄子,P 表示布,S 表示剪子.

Output

Print the maximum number of games Bessie can win, given that she can only change gestures at most \(k\) times.

输出在变化不超过 \(k\) 次的前提下, 最多能赢多少次.

Sample Input

5 1
P
P
H
P
S

Sample Output

4

Explanation

用 \(dp(i, j, k)\) 表示已经出到第 \(i\) 次, 已经换了 \(j\) 次, 当前出的是 \(k\).

转移方程详见代码, 这是一道很水很水的动规题~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
#define maximize(__x,__y) __x=max(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 100100, maxm = 30;
#define HOOF 0
#define SCISSORS 1
#define PAPER 2

const int match[3][3] = { // match[Bessie][FJ]
    { 0, 1, 0 },
    { 0, 0, 1 },
    { 1, 0, 0 } };
int n, K;
int arr[maxn];
int dp[maxn][maxm][3];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) {
        static char str[20];
        scanf("%s", str);
        switch (str[0]) {
            case 'H': arr[i] = HOOF; break;
            case 'S': arr[i] = SCISSORS; break;
            case 'P': arr[i] = PAPER; break;
            default: break;
        }
    }
    // Ere a great dump of complicated reading.
    // Reset the initial states of dp[][][].
    range(0, 2) dp[0][0][_] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= K; j++) {
            for (int k = 0; k <= 2; k++) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j > 0) range(0, 2) if (_ != k)
                    maximize(dp[i][j][k], dp[i - 1][j - 1][_]);
                dp[i][j][k] += match[k][arr[i]];
            }
        }
    }
    // Retrieve result
    int res = 0;
    for (int j = 0; j <= K; j++)
        for (int k = 0; k <= 2; k++)
            maximize(res, dp[n][j][k]);
    printf("%d\n", res);
    return 0;
}