题意简析
- 给你两个长度为 \(n\) 的字符串 \(s,t\)，只有小写字母。
- 定义每次操作为选泽 \(s\) 的一个字串 \(s_l,s_{l+1},...,s_{r-1},s_r\)，然后将它改为 \(s_r,s_l,s_{l+1},...,s_{r-1}\)。
- 求将 \(s\) 改为 \(t\) 的最小次数，无解则输出 \(-1\)。
- 有多组数据，\(\sum n\le 2000\)。
分析
一句话题意：每次可以将一个字符插入它前面的任意一个地方，多少次两字符串相同。
首先，对于每一个字母，如果它在 \(s,t\) 中的出现次数不同，一定无解，输出 \(-1\)。否则有解（每一次都提一个到前面，最多只要 \(n\) 次）。
考虑 dp，发现每个操作都是向前移。我们记 \(dp_{i,j}\) 表示把 \(s\) 中长为 \(i\) 的前缀，把 \(i\) 后的字符向前移动，与 \(t\) 中长为 \(j\) 的前缀相同的最小操作数，这里为了方便，规定 \(i\le j\)。我们就得到了以下几种方案：
- 将 \(s_i\) 往前移不与 \(t_j\) 匹配：\(dp_{i,j}=dp_{i-1,j}+1\)
- 如果 \(s_i=t_j\)，那么可以直接把 \(i\) 移到 \(j\) 上：\(dp_{i,j}=dp_{i-1,j-1}\)
- 如果在 \(i\) 后， \(s\) 中还有 \(t_j\) 字符的存在，那么可以将后面的一个拿过来使用，但是在当前情况下，还没有算上一次操作，它会在后面的某个地方由第一种情况记录进去：\(dp_{i,j}=dp_{i,j-1}\)
最后输出 \(dp_{n,n}\) 即可。复杂度为 \(O(n^2)\)。
总结
统计出现个数，进行 dp 转移。记得边界条件和初始化。一道CF2600的良心题。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
inline int read(){
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)){if (c == ‘-‘) f = -1; c = getchar();}
while (isdigit(c)){x = (x << 3) + (x << 1) + c - ‘0‘; c = getchar();}
return x * f;
}
inline int max(int x, int y){return x > y ? x : y;}
inline int min(int x, int y){return x < y ? x : y;}
int cnt[3][N][30], dp[N][N];
char s[N], t[N];
int main(){
int T = read();
while (T --){
int n = read();
scanf("%s", s + 1);scanf("%s", t + 1);
for (int i = 1; i <= n; i ++){
for (int j = 0; j < 26; j ++)
for (int k = 0; k < 2; k ++)
cnt[k][i][j] = cnt[k][i - 1][j];
++ cnt[0][i][s[i] - ‘a‘];
++ cnt[1][i][t[i] - ‘a‘];
}
bool flag = false;
for (int i = 0; i < 26; i ++)
if (cnt[0][n][i] != cnt[1][n][i]){
puts("-1");
flag = true;
break;
}
if (flag) continue;
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= n; j ++)
dp[i][j] = 0x3f;
for (int i = 0; i <= n; i ++) dp[0][i] = 0;
for (int i = 1; i <= n; i ++){
for (int j = i; j <= n; j ++){
dp[i][j] = dp[i - 1][j] + 1;
if (s[i] == t[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
if (cnt[0][i][t[j] - ‘a‘] < cnt[1][j][t[j] - ‘a‘])
dp[i][j] = min(dp[i][j], dp[i][j - 1]);
}
}
printf("%d\n", dp[n][n]);
}
return 0;
}