【题解】迎接仪式

ctj12461 · 2019-07-27 22:15:08 · 题解

本文/题解首发于https://ctj12461.netlify.com/2019/883e12d。

这是一道DP的题，看懂题目就可以推导出状态转移方程了。

算法分析

题目要求在 K 步之内通过交换字符'j'和'z'，来产生尽可能多的子串"jz"。

我们不妨设 s 为原字符串，设一个三维数组 f_{k,i,j} 来表示在第 k 个字符时，通过改动 i 个'j'、 j 个'z'，最多有多少个"jz"。 k 则从 2 开始枚举。

我们可以进行分类讨论：

• 当 s_{k - 1} = 'j',s_{k} = 'z' 时，很显然， f_{k,i,j} 不需要改动，可以直接用 f_{k-2,i,j}+1 来更新，再取个最大值。

• 当 s_{k - 1} = 'z',s_{k} = 'j' 时，需要交换两个字符的位置，则用 f_{k-2,i-1,j-1}+1 来更新。

• 当 s_{k - 1} = s_{k} = 'j' 时，只需要改动一个'j'为'z'，用 f_{k-2,i-1,j}+1 来更新。

• 当 s_{k - 1} =s_{k} = 'z' 时，类似。

所以我们整理后就是这样了：

再考虑初始化，如果 s_{1} = 'j' ,则 f_{1,1,0}=0，否则 f_{1,0,1}=0.

还有， f_{1,0,0}=f_{0,0,0}=0，其他元素初始化为无穷小。

最后，答案 ans 就是:

因为'j'和'z'的修改次数只有相同时才是有效的。

代码实现

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

char s[501];
int f[501][101][101];

int N, K;

inline int read() {
    int x = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9') {
        if (s == '-')
            f = -f;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = x * 10 + s - '0';
        s = getchar();
    }
    return x * f;
}

int main() {
    N = read();
    K = read();
    scanf("%s", s + 1);
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            for (int l = 0; l <= K; l++) {
                f[i][j][l] = -0x3f3f3f3f;
            }
        }
    }
    if (s[1] == 'j')
        f[1][1][0] = 0;
    else
        f[1][0][1] = 0;
    f[1][0][0] = 0;
    f[0][0][0] = 0;
    int ans = -0x3f3f3f3f;
    for (int k = 2; k <= N; k++) {
        for (int i = 0; i <= K; i++) {
            for (int j = 0; j <= K; j++) {
                f[k][i][j] = f[k - 1][i][j];
                if (s[k - 1] == 'j' && s[k] == 'z')
                    f[k][i][j] = max(f[k][i][j], f[k - 2][i][j] + 1);
                if (s[k - 1] == 'z' && s[k] == 'j' && i && j)
                    f[k][i][j] = max(f[k][i][j], f[k - 2][i - 1][j - 1] + 1);
                if (s[k - 1] == 'z' && s[k] == 'z' && j)
                    f[k][i][j] = max(f[k][i][j], f[k - 2][i][j - 1] + 1);
                if (s[k - 1] == 'j' && s[k] == 'j' && i)
                    f[k][i][j] = max(f[k][i][j], f[k - 2][i - 1][j] + 1);
                if (i == j)
                    ans = max(ans, f[k][i][j]);
            }
        }
    }
    printf("%d", ans);
}