题意描述

LHX教主要来X市指导OI学习工作了。

为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。

一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。

为了简单描述这个不和谐的队列，我们用“$j$”替代“教”，“$z$”替代“主”。而一个”$j$”与“$z$”组成的序列则可以描述当前的队列。

为了让教主看得尽量舒服，你必须调整队列，使得“$jz$”子串尽量多。

每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。

而因为教主马上就来了，时间仅够最多作$k$次调整（当然可以调整不满$k$次），所以这个问题交给了你。

输入格式

第一行包含$2$个正整数$n$与$k$，表示了序列长度与最多交换次数。

第二行包含了一个长度为$n$的字符串，字符串仅由字母“$j$”与字母“$z$”组成，描述了这个序列。

输出格式

一个非负整数，为调整最多$k$次后最后最多能出现多少个“$jz$”子串。

Input & Output ‘s examples

Input ‘s eg

5 2 
zzzjj

Output ‘s eg

样例解释

第$1$次交换位置$1$上的$z$和位置$4$上的$j$，变为$jzzzj$；

第$2$次交换位置$4$上的$z$和位置$5$上的$j$，变为$jzzjz$。

最后的串有$2$个“$jz$”子串。

数据范围与约定

对于$10\%$的数据，有$N≤10$；

对于$30\%$的数据，有$K≤10$；

对于$40\%$的数据，有$N≤50$；

对于$100\%$的数据，有$N≤500,K≤100$。

分析

一道暴力动态规划题。

不难注意到，题目的数据范围极小。因此，我们可以直接大力设计状态

设$f[k][i][j]$表示考虑前$k$个人，通过交换$i$次j，$j$次z的jz数。

然后大力分类讨论，考虑第$k$个人时j还是z。

若第$k - 1$个人为j，第$k$个人为z，则$f[k][i][j]$可以直接用$f[k - 2][i][j]$更新。答案为 $f[k - 2][i][j] + 1$

若第$k - 1$个人为z，第$k$个人为j，则$f[k][i][j]$相当于在$f[k - 2][i][j]$的基础上交换两个字符的位置。答案为 $f[k - 2][i + 1][j + 1] + 1$

若第$k - 1$个人为z，第$k$个人为z，则$f[k][i][j]$相当于在$f[k - 2][i][j]$的基础上将一个z换为j。则答案为 $f[k - 2][i][j + 1] + 1$

若第$k - 1$个人为j，第$k$个人为j，则$f[k][i][j]$相当于在$f[k - 2][i][j]$的基础上将一个j换为z。则答案为 $f[k - 2][i + 1][j] + 1$

大力转移即可。

还有就是，最后答案应为$max{k = 1}^n \lbrace f{k , i , j} , i = j \rbrace$。因为只有当交换次数一致时，答案才是符合题意的。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 501

using namespace std;

ll f[N][150][150];//f[k][i][j]为前i个字符，交换了i次j，j次z。

int n , m;
char s[N];
ll ans = -0x3f3f3f3f;   

int main(){
    cin >> n >> m;
    scanf("%s" , s + 1);
    for(int i = 0; i <= n; i ++){
        for(int j = 0; j <= m; j ++){
            for(int k = 0; k <= m; k ++){
                f[i][j][k] = -0x3f3f3f3f;   //开始时赋初值
            }
        }
    }
    if(s[1] == 'j'){    //同上
        f[1][1][0] = 0;
    }
    else{
        f[1][0][1] = 0;
    }
    f[1][0][0] = 0;
    f[0][0][0] = 0;
    for(int k = 2; k <= n; k ++){
        for(int i = 0; i <= m; i ++){
            for(int j = 0; j <= m; j ++){
                f[k][i][j] = f[k - 1][i][j];    //分情况讨论，转移
                if(s[k - 1] == 'j' && s[k] == 'z'){
                    f[k][i][j] = max(f[k][i][j] , f[k - 2][i][j] + 1);
                }
                if(s[k - 1] == 'z' && s[k] == 'j' && i && j){
                    f[k][i][j] = max(f[k][i][j] , f[k - 2][i - 1][j - 1] + 1);
                }
                if(s[k - 1] == 'z' && s[k] == 'z' && j){
                    f[k][i][j] = max(f[k][i][j] , f[k - 2][i][j - 1] + 1);
                }
                if(s[k - 1] == 'j' && s[k] == 'j' && i){
                    f[k][i][j] = max(f[k][i][j] , f[k - 2][i - 1][j] + 1);
                }
                if(i == j){     
                    ans = max(ans , f[k][i][j]);    //统计合法答案。
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}