这个可以改,你试试dp不要用记忆化,你这个程序dfs的遍历不太好,你用我这个
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 510;
int f[N][120][120], ans = 0;
char s[N];
int main() {
int n,m;
scanf("%d%d%s", &n, &m, s + 1);
memset(f, 0 , sizeof f);
f[0][0][0] = f[1][0][0] = f[1][s[1] == 'j'][s[1] == 'z'] = 0;
for(int i = 2; i <= n; ++i)
for(int j = 0 ; j <= m; ++j)
for(int k = 0; k <= m; ++k) {
f[i][j][k] = f[i - 1][j][k];
if(s[i - 1] == 'j' && s[i] == 'z') f[i][j][k] = max(f[i][j][k], f[i - 2][j][k] + 1);
if(k&&s[i - 1] == 'z' && s[i] == 'z') f[i][j][k] = max(f[i][j][k], f[i - 2][j][k - 1] + 1);
if(j&&s[i - 1] == 'j' && s[i] == 'j') f[i][j][k] = max(f[i][j][k], f[i - 2][j - 1][k] + 1);
if(j&&k&&s[i - 1] == 'z' && s[i] == 'j') f[i][j][k] = max(f[i][j][k], f[i - 2][j - 1][k - 1] + 1);
if(j == k)ans = max(ans, f[i][j][k]);
}
printf("%d\n",ans);
return 0;
}
```
by Dsesert @ 2020-08-30 15:03:22
@[堕魂灭天](/user/362162) dp我能搞,我想试试记搜,不过还是谢谢了。
by 沉鸣cmh @ 2020-08-30 15:47:34
改了下,这样还是不行。
```
#include<bits/stdc++.h>
using namespace std;
int n,k,a[505],su[505][105][3][3],sum;
char oo;
int pd1(int x){
if(x>1)return a[x-1]==0?-1:0;
return 0;
}
int pd2(int x){
if(x<n)return a[x+1]==1?1:0;
return 0;
}
int dfs(int wz,int cs){int th=0;
if(su[wz][cs][a[wz]][a[wz-1]])return su[wz][cs][a[wz]][a[wz-1]];
if(cs==0||wz==n+1)return 0;
if(a[wz]==1){
th=dfs(wz+1,cs),a[wz]=0;
th=max(th,dfs(wz+1,cs-1)+pd1(wz)+pd2(wz));a[wz]=1;
}
else {
th=dfs(wz+1,cs),a[wz]=1;
th=max(th,dfs(wz+1,cs-1)-pd1(wz)-pd2(wz));a[wz]=0;
}
return su[wz][cs][a[wz]][a[wz-1]]=th;
}
int main(){a[0]=3;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>oo;if(oo=='z'){a[i]=1;if(a[i-1]==0)sum++;}else a[i]=0;
}if(k>=n){cout<<n/2;return 0;}
cout<<dfs(1,k)+sum;
return 0;
}
```
我还找不到反例
by 沉鸣cmh @ 2020-08-30 15:48:10
。。。记忆搜做这题不太合适,因为遍历问题。我来试试记忆搜等我一会
by Dsesert @ 2020-08-30 15:57:08
@[堕魂灭天](/user/362162) 好的
by 沉鸣cmh @ 2020-08-30 16:04:52
不行,我的只有10分
这就是动规和贪心,用不上记仪化,用记仪化的话会导致“jz”子串不是最多(有概率最多)
所以我不建议你用记仪化
by Dsesert @ 2020-08-30 16:05:43
正确的是第2次交换位置44上的zz和位置55上的jj,变为**jzzjzjzzjz**。记仪化就变成
**jzzjzzjzjz**
by Dsesert @ 2020-08-30 16:08:41
44打错了应该是4
by Dsesert @ 2020-08-30 16:09:28
55是5
by Dsesert @ 2020-08-30 16:10:06
记仪化比较适合P1278,这题还好,不算难。想练习记仪化的话可以去做
by Dsesert @ 2020-08-30 16:13:24