cf1701e solution

hcywoi · 2022-07-13 20:11:53 · 题解

题目大意

给我们一个字符串 s 和字符串 t，我们可以给字符串 s 做以下操作：

• 把光标向左移
• 把光标向右移
• 删除一个字符
• 把光标移到开头
• 把光标移到结尾

问：把 s 变成 t，最少的操作次数。

解题思路

我们会发现最优解中一定可以先操作后面，再移动到开头操作前面。

然后我们可以前面做一遍 Dp，在从后面做一遍 Dp。

• 如果删除，f_{i,j}=f_{i-1,j}+2

设 s_{1 \sim i} 和 t_{1 \sim j} 匹配的最小值为 f_{i, j}^{'}。

如果 s_i = s_j，且不用删除是小于删除的，那么 f_{i, j}^{'} = f_{i-1,j-1}^{'}。否则 f_{i,j}^{'}=f_{i-1,j}+2

后面做一遍 Dp 与前面类似，就不在赘述。

最后在把所有方案求一个最小值。

Ac Code

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;
const short INF = N;

int n, m;
short f[N][N], g[N][N];
short fp[N][N], gp[N][N];
char s[N], t[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        scanf("%s%s", s + 1, t + 1);
        for (int i = 0; i <= n + 1; i ++ )
            for (int j = 0; j <= m + 1; j ++ )
                f[i][j] = g[i][j] = fp[i][j] = gp[i][j] = INF; // 初始化

        f[0][0] = fp[0][0] = 0;
        for (int i = 1; i <= n; i ++ ) // 从前面做 Dp
            for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = fp[i][j] = f[i - 1][j] + 2;
                if (j && s[i] == t[j])
                {
                    if (f[i][j] >= f[i - 1][j - 1] + 1)
                    {
                        f[i][j] = f[i - 1][j - 1] + 1;
                        fp[i][j] = fp[i - 1][j - 1];
                    }
                }
            }

        g[n + 1][m + 1] = gp[n + 1][m + 1] = 0;
        for (int i = n; i; i -- ) // 从后面做 Dp
            for (int j = m + 1; j; j -- )
            {
                g[i][j] = gp[i][j] = g[i + 1][j] + 1;
                if (j <= m && s[i] == t[j])
                {
                    if (g[i][j] >= g[i + 1][j + 1] + 1)
                    {
                        g[i][j] = g[i + 1][j + 1] + 1;
                        gp[i][j] = gp[i + 1][j + 1];
                    }
                }
            }
        short res = INF;
        for (int i = 0; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
                res = min(res, short(fp[i][j] + gp[i + 1][j + 1] + (fp[i][j] > 0 ? 1 : 0)));
// 求最小值，如果从前面是选 fp[i,j]，那么从后面就是 gp[i + 1, j + 1]
        if (res >= INF) res = -1;
        printf("%d\n", res);
    }

    return 0;
}