原题链接
普通的(DP)题，然而我又做了好久，太菜了。
很容易发现直接描述“交换”这一操作比较困难，于是我们可以考虑将这一操作转换一下：交换一个j和z，实际上就是将一个z变为j，一个j变为z。
那么我们可以求出当(j)个j变为z，(k)个z变为j时最多能出现的jz个数。而“交换”这一操作就是当(j=k)的情况（我们不必考虑到底是哪几个j与z交换了）。
定义(f[i][j][k][0/1])表示前(i)个字符中，有(j)个j变为z，(k)个z变为j，且第(i)个字符是j（用(1)表示）或z（用(0)表示）的时候，最多能出现的jz个数。
于是有状态转移方程：
- 第(i)个字符为
j时
先直接从前(i-1)个字符的情况转移过来：$$f[i][j][k][1] = max{f[i - 1][j][k][0], f[i - 1][j][k][1]}$$
当(j > 0)时，则可以将第(i)个字符j转换为z，于是有：$$f[i][j][k][0] = max{ f[i - 1][j - 1][k][0], f[i - 1][j - 1][k][1] + 1 }$$
- 第(i)个字符为
z时
同样先直接从前(i-1)个字符的情况转移过来，不过注意前一个为j时可以和当前这个z组成jz：$$f[i][j][k][0] = max{f[i - 1][j][k][0], f[i - 1][j][k][1] + 1}$$
当(k > 0)时，则可以将第(i)个字符z转换为j，于是有：$$f[i][j][k][1] = max{ f[i - 1][j][k - 1][0], f[i - 1][j][k - 1][1] }$$
初始化(f[0][0][0][0] = 0)，其余为(-infty)。
答案显然就是(maxlimits_{i = 1} ^ n{ f[n][i][i][0], f[n][i][i][1] })。
时间复杂度(O(nm^2))，另外(f)的第一维是可以滚掉的，不过这题数据小也就不需要了。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 510;
const int M = 110;
int f[N][M][M][2], a[N];
inline int re_l()
{
char c = getchar();
for (; c != 'z' && c != 'j'; c = getchar());
return c == 'z' ? 0 : 1;
}
inline int maxn(int x, int y) { return x > y ? x : y; }
int main()
{
int i, j, k, n, m, ans = -1e9;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
a[i] = re_l();
memset(f, 195, sizeof(f));
f[0][0][0][0] = 0;
for (i = 1; i <= n; i++)
for (j = 0; j <= m; j++)
for (k = 0; k <= m; k++)
if (a[i])
{
f[i][j][k][1] = maxn(f[i - 1][j][k][0], f[i - 1][j][k][1]);
if (j)
f[i][j][k][0] = maxn(f[i - 1][j - 1][k][0], f[i - 1][j - 1][k][1] + 1);
}
else
{
f[i][j][k][0] = maxn(f[i - 1][j][k][0], f[i - 1][j][k][1] + 1);
if (k)
f[i][j][k][1] = maxn(f[i - 1][j][k - 1][0], f[i - 1][j][k - 1][1]);
}
for (i = 1; i <= n; i++)
ans = maxn(ans, maxn(f[n][i][i][0], f[n][i][i][1]));
return printf("%d", ans), 0;
}