【GMOJ5102】小学生语文题

题目

题目链接：https://gmoj.net/senior/#main/show/5102

(Qleq 10,nleq 2000)。

思路

下文把第一个串称作 (s) 串，第二个串称作 (t) 串。
假设我们从后往前考虑，如果要把位置 (i) 往前移到 (j)，可以看做枚举到位置 (i) 的时候把位置 (i) 的字符拎出来，枚举到 (j) 的时候再放下去。
设 (f[i][j]) 表示 (t) 串第 (jsim n) 位中，拎出了 (i-j) 个字符没有放回去，剩余 (n-i) 个字符依次排到最后与 (s) 串 (isim n) 恰好匹配时，最小的操作次数。
那么 (f[i][j]) 有三种转移方式：

• (f[i][j]=f[i+1][j])：当 (t[jsim n]) 中字符 (s[i]) 的出现次数严格大于 (s[i+1sim n]) 中字符 (s[i]) 的出现次数。
• (f[i][j]=f[i+1][j+1])：当 (s[i]=t[i]) 时，这两位可以直接匹配上。
• (f[i][j]=f[i][j+1]+1)：把 (t[j]) 拎出来。

最后答案就是 (f[1][1])。
至于输出方案，我们发现只有进行第二种转移时才不需要多移动，否则直接往后暴力找到一个相同的字符暴力移动一下即可。
时间复杂度 (O(Qn^2))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=2010;
int Q,n,f[N][N],pre[N][N][2],cnt[2][N][26];
char s[N],t[N];
bool flag[2][N];

int main()
{
	freopen("chinese.in","r",stdin);
	freopen("chinese.out","w",stdout);
	scanf("%d",&Q);
	while (Q--)
	{
		memset(f,0x3f3f3f3f,sizeof(f));
		memset(flag,0,sizeof(flag));
		memset(cnt,0,sizeof(cnt));
		scanf("%s%s",s+1,t+1);
		n=strlen(s+1);
		for (int i=n;i>=1;i--)
			for (int j=0;j<26;j++)
			{
				cnt[0][i][j]=cnt[0][i+1][j]+(s[i]-'a'==j);
				cnt[1][i][j]=cnt[1][i+1][j]+(t[i]-'a'==j);
			}
		for (int i=1;i<=n+1;i++) f[n+1][i]=n-i+1;
		for (int i=n;i>=1;i--)
			for (int j=i;j>=1;j--)
			{
				if (cnt[1][j][s[i]-'a']>cnt[0][i+1][s[i]-'a'] && f[i][j]>f[i+1][j])
					f[i][j]=f[i+1][j],pre[i][j][0]=i+1,pre[i][j][1]=j;
				if (s[i]==t[j] && f[i][j]>f[i+1][j+1])
					f[i][j]=f[i+1][j+1],pre[i][j][0]=i+1,pre[i][j][1]=j+1;
				if (f[i][j]>f[i][j+1]+1)
					f[i][j]=f[i][j+1]+1,pre[i][j][0]=i,pre[i][j][1]=j+1;
			}
		for (int i=1,j=1;i<=n;)
		{
			if (pre[i][j][0]==i+1 && pre[i][j][1]==j+1)
				flag[0][i]=flag[1][j]=1;
			int x=i,y=j; i=pre[x][y][0]; j=pre[x][y][1];
		}
		cout<<f[1][1]<<"
";
		for (int i=1;i<=n;i++)
			if (!flag[0][i])
				for (int j=i+1;j<=n;j++)
					if (!flag[1][j] && s[i]==t[j])
					{
						cout<<j<<" "<<i<<"
";
						flag[1][j]=1;
						for (int k=j;k>i;k--)
						{
							swap(flag[1][k],flag[1][k-1]);
							swap(t[k],t[k-1]);
						}
						break;
					}
	}
	return 0;
}