记录
2026-07-16 17:40:18
发布于：浙江
20阅读
0回复
0点赞
第 道青，详细的写了一下，看代码吧。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace syh;
const int maxn=505;//字符串最大长度
const int maxk=105;//最大交换次数
const int inf=0xc0c0c0c0;//负无穷，用与对应memset初始化
int dp[maxn][maxk][maxk][2], n, k, ans=0;
//dp[i][j][z][l]
//i:处理第i个字符
//j:有多少个'j'变为'z'
//z:有多少个'z'变为'j'
//l:第i个字符最终是'j'还是'z'
//dp元素的值:最多有多少个'jz'子串
string s;
int main()
{
memset(dp,0xc0,sizeof dp);//初始化为负无穷
cin>>n>>k>>s;//读入长度、交换次数、字符串
int fir=(s[0]=='j')?0:1;//第1个字符，是'j'就为0，是'z'就为1
if(fir==0)//第一个是'j'
{
dp[1][0][0][0]=0;//不变，j到z为0，z到j为0，当前是j
if(k>=1) dp[1][1][0][1]=0;//'j'变成'z'，j为1，当前是z
}
else//第一个是'z'
{
dp[1][0][0][1]=0;//不变，j到z为0，z到j为0，当前是z
if(k>=1) dp[1][0][1][0]=0;//'z'变成'j'，z为1，当前是j
}
for(int i = 2;i<=n;i++)//从第二个字符开始dp，因为第一个已经处理了
{
int c=(s[i-1]=='j')?0:1;//当前位置原来是什么（'j'还是'z'）
for(int j = 0;j<=k;j++)//枚举j到z的次数
{
for(int z = 0;z<=k;z++)//枚举z到j的次数
{
for(int l = 0;l<=1;l++)//枚举前一个字符最终是什么
{
if(dp[i-1][j][z][l]==inf) continue;//无效状态*
for(int cu = 0;cu<=1;cu++)//枚举当前位置最终变成什么
{
int nj=j, nz=z;//当前j变z的次数和z变j的次数
if(c==0&&cu==1) nj++;//原j变z，次数加一
if(c==1&&cu==0) nz++;//原z变j，次数加一
if(nj>k||nz>k) continue;//某个变化次数超过了规定就跳过，不进入下面的dp
int a=(l==0&&cu==1)?1:0;//判断是否组成'jz'（前面是'j'现在是'z'）
dp[i][nj][nz][cu]=max(dp[i][nj][nz][cu],dp[i-1][j][z][l]+a);//更新dp值*
}
}
}
}
}
for(int i = 0;i<=k;i++)//枚举j到z与z到j相等的情况*
{
for(int l = 0;l<=1;l++)//枚举最后一个字符（两种可能）*
{
ans=max(ans,dp[n][i][i][l]);//只有j与z相等才是合法的交换*
}
}
cout<<max(0,ans);//答案至少为0，打擂输出
}
//无效状态*:值为inf的说明没有被计算过，出现不了这种状态所以要跳过
//更新dp值*:打擂更新前i-1个字符的最优值加上现在的子串数与原先的最优数量的最大值作为现在的最优值
//枚举j到z与z到j相等的情况*:因为交换必须成对出现，所以j到z的数量必须为z到j的数量
//枚举最后一个字符（两种可能）*:因为经过交换后最后一个字符的值可能发生变化，所以要枚举所有情况（j或z）才能更新最大值
//只有j与z相等才是合法的交换*:因为有两种情况，所以要选择最后为j或z的最大值，i=i是因为j到z的次数与z到j的次数一定相等，dp[n][][][]是因为已经处理了整个字符串，变化到第n个才能知道最终的答案
不是题解不是口胡是记录！！
有帮助，赞一个