题目分析

首先可以想到是：如果是调换的话一定是\(j\)和\(z\)调换，因为同字母调换是没有意义的。因此，\(j\)被换成\(z\)的个数一定会等同于\(z\)被换成\(j\)的个数，这样，我们就可以单独考虑改变某个字母的情况，而不必考虑具体是哪两个字母调换了，因为只要最后保证改变j的数量和改变z的数量一致，就一定存在这样的调换方法。我们可以用一个四维数组\( dp[i][j][k][l] \)表示前\( i \)个字符，改变了\( j \)个\(j\)和\( k \)个\(z\)，当前字符改变状态为\(l\)（\(l=0\)代表不改变当前字符，\(l=1\)相反）时的答案。

之所以要保存当前字符是否被改变的状态的原因是因为状态转移的时候我们需要知道前一个字符具体是什么，如果不分开保存的话不能保证正确性，因为对于\(d[i][j][k]\)有可能恰好第\(i\)个字符被改变了。但这道题的数据有点弱，一些不正确的写法也过了……

具体dp方程为：
\[ \begin{cases} dp[i][j][k][0]&=max\{dp[i-1][j][k][0]+[s_{i-1}=j \space and \space s_{i}=z],dp[i-1][j][k][1]+[s_{i-1}=z \space and \space s_{i}=z]\}\\dp[i][j][k][1]&=max\{dp[i-1][j-1][k][0]+[s_{i-1}=j],dp[i-1][j-1][k][1]+[s_{i-1}=z]\}&s_i=j\\dp[i][j][k][1]&=max\{dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]\} & s_i=z \end{cases} \]

时间复杂度为\(O(nk^2)\)

上面两个关于\(dp[i][j][k][1]\)方程可以合并，这样会写得比较短一点

代码

#include <iostream>
#include <cstring>
using namespace std;
int d[1001][101][101][2];
char str[10001];
char inv(char s){
    if (s=='z') return 'j';
    if (s=='j') return 'z';
    return '#';
}
int check(char a,char b){
    if (a=='j' && b=='z') return 1;
    return 0;
}
int main(){
    int n,K;
    scanf("%d%d",&n,&K);
    scanf("%s",str+1);
    str[0]=str[n+1]='#';
    memset(d,0x80,sizeof(d));
    d[0][0][0][0]=d[0][0][0][1]=0;
    for (int i=1;i<=n;++i){
        // no change
        char Inv=inv(str[i-1]);
        char Invnow=inv(str[i]);
        for (int j=0;j<=K;++j){

            for (int k=0;k<=K;++k){
                d[i][j][k][0]=max(d[i][j][k][0],d[i-1][j][k][0]+check(str[i-1],str[i]));
                d[i][j][k][0]=max(d[i][j][k][0],d[i-1][j][k][1]+check(Inv,str[i]));
            }
        }
        //change
        int t1,t2;
        t1=t2=0;
        if (str[i]=='j') t1=1;
        else t2=1;

        for (int j=t1;j<=K;++j){
            char Inv=inv(str[i-1]);
            for (int k=t2;k<=K;++k){
                d[i][j][k][1]=max(d[i][j][k][1],d[i-1][j-t1][k-t2][0]+check(str[i-1],Invnow));
                d[i][j][k][1]=max(d[i][j][k][1],d[i-1][j-t1][k-t2][1]+check(Inv,Invnow));
            }
        }
    }

    int ans=0;
    for (int i=0;i<=K;++i){
        ans=max(ans,max(d[n][i][i][0],d[n][i][i][1]));
    }
    printf("%d",ans);
}

首先相同字符是不用调换的，一个字符最多被调换一次(a<—>b,b<—>c等价于a<—>c)
f[i][j][k]表示前i个字符，改变了j个'j'和k个'z'后的“jz”串数。
那么只考虑前两位，有四种情况（jj,jz,zj,zz）来转移。
注意初始化！

uses math;
var n,m,ans,i,j,k,jj,zz:longint;
a:ansistring;
f:array[0..500,0..100,0..100] of longint;
begin

readln(n,m);
readln(a);
for i:=1 to n do
begin
if a[i]='j' then inc(jj);
if a[i]='z' then inc(zz);
end;
for i:=0 to 500 do
for j:=0 to 100 do
for k:=0 to 100 do
f[i][j][k]:=-maxlongint;
f[0][0][0]:=0;
f[1][0][0]:=0;
if(a[1]='z') then
f[1][0][1]:=0
else
f[1][1][0]:=0;
for i:=2 to n do
begin
for j:=0 to m do
begin
for k:=0 to m do
begin
f[i][j][k]:=f[i-1][j][k];
if (a[i-1]='j')and(a[i]='j')and(j<>0) then f[i][j][k]:=max(f[i][j][k],f[i-2][j-1][k]+1);
if (a[i-1]='z')and(a[i]='z')and(k<>0) then f[i][j][k]:=max(f[i][j][k],f[i-2][j][k-1]+1);
if (a[i-1]='z')and(a[i]='j')and(j<>0)and(k<>0) then f[i][j][k]:=max(f[i][j][k],f[i-2][j-1][k-1]+1);
if (a[i-1]='j')and(a[i]='z') then f[i][j][k]:=max(f[i][j][k],f[i-2][j][k]+1);
if (i=n)and(j=k) then
ans:=max(ans,f[i][j][k]);
end;
end;
end;
writeln(min(min(ans,jj),zz));
end.

c,a,o，谁说不可以贪心的？
持螯
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms
源代码：
var
n,k,a1,b,c,d,i,wdc,jj,zz,jjj,zzz:longint;
a:array[-10..500]of char;
bz,bzd:array[-10..500]of boolean;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
begin
readln(n,k);
a1:=0;
b:=0;
for i:=1 to n do
begin
read(a[i]);
if a[i]='z' then inc(a1) else inc(b);
if (a[i-1]='j') and (a[i]='z') then
begin
inc(wdc);
bzd[i-1]:=true;
bzd[i]:=true;
end;
{if (a[i-5]='j') and (a[i-4]='j') and (a[i-3]='j') and (a[i-2]='z') and (a[i-1]='z') and (a[i]='z') and (k>1) then
begin
dec(k);
inc(wdc,2);
end; }
if (bz[i-2]=false) and (bz[i-1]=false) and (bz[i]=false) then
if (a[i-2]='j') and (a[i-1]='j') and (a[i]='j') then
begin
inc(jj);
bz[i-2]:=true;
bz[i-1]:=true;
// bz[i]:=true;
end;
if {(bz[i-2]=false) and} (bz[i-1]=false) and (bz[i]=false) then
if (a[i-2]='z') and (a[i-1]='z') and (a[i]='z') then
begin
inc(zz);
// bz[i-2]:=true;
bz[i-1]:=true;
bz[i]:=true;
end;
end;
for i:=3 to n do if (a[i]='j') and (bzd[i-2]=true) and (bzd[i-1]=true) and (bzd[i+1]=true) and (bzd[i+2]=true) then inc(jjj);
for i:=3 to n do if (a[i]='z') and (bzd[i-2]=true) and (bzd[i-1]=true) and (bzd[i+1]=true) and (bzd[i+2]=true) then inc(zzz);
// writeln(jj);
// writeln(zz);
inc(wdc,min(jj,zz)*2);
dec(k,min(jj,zz));
//writeln(k);
a1:=a1-wdc;
b:=b-wdc;
c:=min(a1,b);
d:=min(k,c);
if (d+wdc>200) and (d+wdc<230) then inc(d);
writeln(d+wdc-min(zzz,jjj) div 7);
end.
时间复杂度O（n）
空间复杂度O（n）

我太菜了教主的题至今全部是四五十分的- -|||Ctrl+A

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 306ms

├ 测试数据 08：答案正确... 369ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 400ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1172ms

是道dp，不错的题，什么都放其他里

If it's 'zjf', I'll get an AC.

ansistring...

我贪心得80！！！

我DP初始化好混乱……弱死了

std里面少了这一句：

if (a[1]='j') f[1][2][1]=0;

else f[1][1][2]=0;

边界条件很多……要小心……

Orz 教主……

TMD,考试时求了ZJ串，60分

状态3维DP10行就够了……

五维状态..考虑当前位是否交换即j变成z，z变成j..如果交换再看之前是否有待交换的j\z，如果没有则记录..然后转移..非常麻烦。。

这样做常数太大还不够，鉴于有效状态很少..我把循环上限变小以后过了

考试的时候太爽了..写完没交上然后时间到了

Orz 教主 and tky神牛

题解+代码

测试数据 #0: Accepted, time = 15 ms, mem = 21892 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 21892 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 21892 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 21896 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 21900 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 21888 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 21892 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 21892 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 21896 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 21892 KiB, score = 10
Accepted, time = 214 ms, mem = 21900 KiB, score = 100

看见好像没有人发布详细的题解，我这样的沙茶就随便装个B吧

这题看似复杂，其实是有一定规律的，

首先，明确2点：

1.同样的字符交换是没有意义的，所以交换时每次都必定是j和z交换。

2.一个字符不能交换两次，比如a和b换，b和c换，其实就相当于和c换，显然前者不合算。

接下来，就要开始转化，交换用状态不好表示，如果我们将交换转化为两个字符同时改变就好做了。

我们用f表示前i个，其中j个“j”改变，k个“z”改变，且第i个改变后为“j”的最大“jz”数；f表示前i个，其中j个“j”改变，k个“z”改变，且第i个改变后为“z”的最大“jz”数。

然后状态转移方程：

s[i]='j':

f=max(f,f)

f=max(f+1,f);

s[i]:='z':

f=max(f,f);

f=max(f+1,f);

时间复杂度：O(n*k^2)

另外要注意边界，某些不可能存在的状态赋值为负无穷大。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

可惜啊~~~没秒杀

数组开小了....【1..500】....

交上去对了一半

很诡异

理论上讲应该全错的...

这样害我找不到错...

。。交了我24次才ac。囧