Description
Data Constraint
Solution
这道题考场上没想到可以倒着dp，感觉dp都白学了。 我们设出f[i][j]表示当前正确串匹配到i，原串匹配到j，i正对着j，i-n中的每个字符j-n中都可匹配的最小步数。我们现在考虑转移。 1、假设当前的j+1我们对其进行操作使它往前丢，那么f[i][j]=f[i][j+1]+1。 2、假设当前的s[i]==s1[j]，那么f[i][j]=f[i+1][j+1]。 3、假设之前往前丢的点中存在s[i],就让他丢到这里，因为那么f[i][j]=f[i+1][j]. 问题是如何输出方案。 我们可以设出g[i][j]表示更新f[i][j]的是哪个点，根据上面的定义确定该点假如是要插入，就把它打上标记。我们从后往前遍历，遇到不匹配的就看他是否有标记，没有就把它丢入桶中，有就从桶中取出字符。最后我们还要处理相对位置问题，暴力的O(N^2)判一下假如发现一个点在前面输出的操作之间就+1。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=
2e3+
5;
struct code{
int x,y;
}g[maxn][maxn],ans1[maxn];
int f[maxn][maxn],c[maxn][
27],d[maxn][
27],sum[
27],bz[maxn],q[
27],g1[maxn];
int m,n,i,t,j,k,l,x,y,z,xx,yy,num,num1,mi;
char s[maxn],s1[maxn];
int main(){
freopen(
"chinese.in",
"r",stdin);freopen(
"chinese.out",
"w",stdout);
scanf(
"%d\n",&m);
while (m){m--;
scanf(
"%s\n",s+
1);
scanf(
"%s\n",s1+
1);n=
strlen(s+
1);
memset(c,
0,
sizeof(c));
memset(d,
0,
sizeof(d));
memset(g1,
0,
sizeof(g1));
memset(q,
0,
sizeof(q));
memset(sum,
0,
sizeof(sum));
memset(f,
127,
sizeof(f));
for (i=n;i>=
1;i--){
for (j=
0;j<
26;j++)
d[i][j]=d[i+
1][j],c[i][j]=c[i+
1][j];
d[i][s[i]-
97]++;c[i][s1[i]-
97]++;
}
for (i=
1;i<=n+
1;i++)f[n+
1][i]=n+
1-i,g[n+
1][i].x=n+
1,g[n+
1][i].y=i+
1;
for (i=n;i>=
1;i--){
for (j=i;j>=
1;j--){
f[i][j]=f[i][j+
1]+
1,g[i][j].x=i,g[i][j].y=j+
1;
if (d[i][s[i]-
97]<=c[j][s[i]-
97]&&f[i+
1][j]<f[i][j]) f[i][j]=f[i+
1][j],g[i][j].x=i+
1,g[i][j].y=j;
if (s[i]==s1[j]&&f[i+
1][j+
1]<f[i][j]) f[i][j]=f[i+
1][j+
1],g[i][j].x=i+
1,g[i][j].y=j+
1;
}
}
printf(
"%d\n",f[
1][
1]);
x=
1;y=
1;
memset(bz,
0,
sizeof(bz));
while (f[x][y]){
xx=g[x][y].x;yy=g[x][y].y;
if (xx==x+
1 && yy==y) bz[x]=
1;
x=xx;y=yy;
}k=
0;j=n;i=n;num=
0;
while (j){
if (s1[i]==s[j]){
i--;j--;
continue;
}
if (!bz[j]) f[s1[i]-
97][++sum[s1[i]-
97]]=i,i--;
else{
ans1[++num].x=f[s[j]-
97][++q[s[j]-
97]],ans1[num].y=i+
1;
j--;k++;
}
}
for (i=
1;i<=num;i++)
for (j=i+
1;j<=num;j++)
if (ans1[i].x>ans1[j].x && ans1[i].y<ans1[j].x) ans1[j].x++;
for (i=
1;i<=num;i++)
printf(
"%d %d\n",ans1[i].x,ans1[i].y);
}
}
