题目链接
题目大意
给定一个长度为 \(N\) 的字符串 \(S\)，\(S\) 仅由字符 \(j , z\) 组成
现在你最多可以执行 \(0\) 到 \(K\) 次操作，每次操作可以选择字符串任意两个位置的字符将它们的位置交换
问最多可以组成多少对相邻的 \((j,z)\)
解题思路
很巧妙的一道题
定义 \(dp[i][j][k][l]\) ，\(1≤i，j，k≤N\) ， \(0≤l≤2\)
其中 \(dp[i][j][k][0]\) 表示前 \(i\) 个字符，改变了 \(j\) 个字符 \(j\) ，\(k\) 个字符 \(z\)，且将第 \(i\) 位字符变为 \(j\) 的最优解
\(dp[i][j][k][0]\) 表示前 \(i\) 个字符，改变了 \(j\) 个字符 j，\(k\) 个字符 \(z\)，且将第 \(i\) 位字符变为 \(z\) 的最优解
那么不难得到 ：
当 \(s[i] = j\) 时
\(dp[i][j][k][0] = max(dp[i - 1][j][k][0] , dp[i - 1][j][k][1])\)
\(dp[i][j][k][1] = max(dp[i - 1][j - 1][k][0] + 1 , dp[i - 1][j - 1][k][1])\)
当 \(s[i] = z\) 时
\(dp[i][j][k][0] = max(dp[i - 1][j][k - 1][0] , dp[i - 1][j][k - 1][1])\)
\(dp[i][j][k][1] = max(dp[i - 1][j][k][0] + 1 , dp[i - 1][j][k][1])\)
最后只要枚举 \(j , k\) 当 \(j = k\) 时更新答案即可
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int M = 5e2 + 10 , MM = 1e2 + 10;
int dp[M][MM][MM][2];
char s[M];
signed main()
{
ios::sync_with_stdio(false);
int n , m;
cin >> n >> m >> s + 1;
memset(dp , 128 , sizeof dp);
dp[0][0][0][1] = 0;
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 0 ; j <= m ; j ++) for(int k = 0 ; k <= m ; k ++)
{
if(s[i] == 'j')
{
int b = max(dp[i - 1][j][k][0] , dp[i - 1][j][k][1]);
dp[i][j][k][0] = max(dp[i][j][k][0] , b);
int d = -0x3f3f3f3f;
if(j) d = max(dp[i - 1][j - 1][k][0] + 1 , dp[i - 1][j - 1][k][1]);
dp[i][j][k][1] = max(dp[i][j][k][1] , d);
}
else
{
int b = -0x3f3f3f3f;
if(k) b = max(dp[i - 1][j][k - 1][0] , dp[i - 1][j][k - 1][1]);
dp[i][j][k][0] = max(dp[i][j][k][0] , b);
int d = max(dp[i - 1][j][k][0] + 1 , dp[i - 1][j][k][1]);
dp[i][j][k][1] = max(dp[i][j][k][1] , d);
}
}
}
int res = 0;
for(int j = 0 ; j <= m ; j ++) for(int k = 0 ; k <= m ; k ++)
{
if(j == k) res = max(res , max(dp[n][j][k][0] , dp[n][j][k][1]));
}
cout << res << '\n';
return 0;
}