题解：CF1363F Rotating Substrings

题意简析

• 给你两个长度为 \(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;
}

题解：CF1363F Rotating Substrings

原文：https://www.cnblogs.com/1314cqy/p/15120228.html