• 给定一个仅由j与z组成的的字符串
  • 允许最多交换KK次字符串中字符
  • 使得字符串中jz子串尽量多

思路

看到这道题之后，我就想要暴力求解，然后。。就没有然后了

思路的关键之处在于，交换kk次，其实意味着kk个j变成z，kk个z变成j。

于是，我们就开心的开始DP了

DP

状态

设f(i,j,z)f(i,j,z)表示前ii位中有jj个j变成了z，有zz个z变成了j

则，对于f(i,j,z)f(i,j,z)，有：

f(i,j,z)=max(f(i−2,j−1,z),f(i−2,j,z−1),f(i−2,j−1,z−1),f(i−2,j,z)) f(i,j,z)=\max(f(i-2,j-1,z),f(i-2,j,z-1),f(i-2,j-1,z-1),f(i-2,j,z))

状态解释:

f(i−2,j−1,z)f(i-2,j-1,z):字符串第i−1i-1位为j，第ii位为j

f(i−2,j,z−1)f(i-2,j,z-1):字符串第i−1i-1位为z，第ii位为z

f(i−2,j−1,z−1)f(i-2,j-1,z-1):字符串第i−1i-1位为z，第ii位为j

f(i−2,j,z)f(i-2,j,z):字符串第i−1i-1位为j，第ii位为z。

只有在f(i,j,z)f(i,j,z)中j=zj=z时才可更新答案，因为此时才满足题意中成对更新的意义

代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
const int MAXN = 500;
const int MAXK = 100;
char a[MAXN + 1];
int f[MAXN + 1][MAXK + 1][MAXK + 1];
int n, k;
int dp () {
    f[0][0][0] = 0, f[1][0][0] = 0;
    int ans = 0; int x, y;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= k; j++)
            for (int z = 0; z <= k; z++) {
                f[i][j][z] = f[i - 1][j][z];
                if (a[i - 1] == 'z') x = 1; else x = 0;
                if (a[i] == 'j') y = 1; else y = 0; //小表，判断应该如何转移
                if (j >= x && z >= y) f[i][j][z] = std::max(f[i][j][z], f[i - 2][j - x][z - y] + 1);
                if (j == z) ans = std::max(ans, f[i][j][z]);//满足条件时更新答案
            }
    return ans;
}
int main () {
    freopen("welcome.in", "r", stdin);
    freopen("welcome.out", "w", stdout);
    scanf("%d %d", &n, &k);
    scanf("%s", a + 1);
    memset(f, -0x777f, sizeof(f));
    printf("%d\n", dp());
    fclose(stdin); fclose(stdout);
    return 0;
}

不得不说这题的转移实在是难想，果然我还是个小蒟蒻qwq