题解 CF1363F 【Rotating Substrings】

· · 题解

CF思维题。

观察操作的本质，就是把一个字符拿出来塞到另一个位置（感性分析

要使操作数最小可以想到使用DP。

我们需要一个N^2算法，所以可以定义N^2的状态。

现在你肯定会问$i$和$j$不相等，也就是两个串长度不相等怎么匹配啊。 我们从$S$串的$i+1\sim N$先借$j-i$个与$T$串匹配。 这样我们就有三种转移。 第一种是直接匹配 $S_i=T_j$时，$f[i][j]=f[i-1][j-1]

第二种是从后面借一个字符

对于当前f[i][j]，S串后面有多余的字符T_j才可以借，否则借了换不起。

在满足有多余字符情况下，这时f[i][j]=f[i][j-1]+1

第三种是还先前借的字符。因为先前保证还的起，所以现在直接还回去即可，不需要条件。

这时，f[i][j]=f[i-1][j]，即把第i个字符还回去。

Attention

其实读到这里你还没有发现这篇题解与前两篇题解有什么区别。。。

我发题解因为想一个细节想了很久。

就是在还的操作时，如果当前字符S_i没有被借过，直接还不显然是错的？

比如\texttt{azaaa,aaaaz}。

这里f[2][2]可以由f[1][2]转移，但是显然f[2][2]是不存在的。

但仔细琢磨下会发现我们更新了f[2][2]对答案并没有影响，因为这里还了一个没有借过的字符，那么后面匹配的时候肯定会少一个字符，匹配不能正常进行。上面的例子发现f[2][2]只能影响状态f[3][3],f[4][4]，不可能对f[i][5]产生影响。

所以并不会影响答案。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 2005
using namespace std;
int n;char s[N],t[N];
int f[N][N],u[N][28],v[N][28];
void solve(){
    scanf("%d",&n);
    scanf("%s%s",s+1,t+1);
    memset(u,0,sizeof(u));
    memset(v,0,sizeof(v));
    rep(i,1,n)u[i][s[i]-'a']++,v[i][t[i]-'a']++;
    rep(i,1,n)rep(j,0,25)u[i][j]+=u[i-1][j],v[i][j]+=v[i-1][j];
    rep(i,0,25)if(u[n][i]!=v[n][i]){puts("-1");return ;}
    rep(i,0,n)rep(j,0,n)f[i][j]=0x3f3f3f3f;
    rep(i,0,n)f[0][i]=0;
    rep(i,1,n){
        rep(j,i,n){
            f[i][j]=f[i-1][j]+1;
            if(s[i]==t[j])f[i][j]=min(f[i-1][j-1],f[i][j]);
            if(u[i][t[j]-'a']<v[j][t[j]-'a'])f[i][j]=min(f[i][j],f[i][j-1]);
        }
    }
    printf("%d\n",f[n][n]);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}
/*
1
3
aab
aba
*/