# F. Rotating Substrings(dp)

2021-08-10 10:17:47

## F. Rotating Substrings(dp)

Ideas ： d p dp dp, Find the maximum number of matches and use n n n To reduce , Because each letter can only move once at most .

set up d p [ i ] [ j ] dp[i][j] dp[i][j] by S S S Middle front of string i i i Characters and T T T Middle front of string j j j Maximum match of characters .

Pay attention when transferring the state, because each operation character moves to the left , So we have to satisfy i ≤ j i\leq j ij, Otherwise, it will never match .

Transfer equation ：

{ d p [ i + 1 ] [ j ] = m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j ] ) , ( i < n ) d p [ i ] [ j + 1 ] = m a x ( d p [ i ] [ j + 1 ] , d p [ i ] [ j ] ) , ( j < n ) \begin{cases}dp[i+1][j]=max(dp[i+1][j],dp[i][j]),(i<n)\\dp[i][j+1]=max(dp[i][j+1],dp[i][j]),(j<n)\end{cases} {dp[i+1][j]=max(dp[i+1][j],dp[i][j]),(i<n)dp[i][j+1]=max(dp[i][j+1],dp[i][j]),(j<n)

{ d p [ i + 1 ] [ j + 1 ] = m a x ( d p [ i + 1 ] [ j + 1 ] , d p [ i ] [ j ] ) ( S [ i ] = = T [ j ] And full foot S in front i individual the Yes Yes Should be word mother Count Small On etc. On T in word mother Count ) \begin{cases}dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j])\\(S[i]==T[j] And meet S Middle front i The number of all corresponding letters is less than or equal to T Medium letter number )\end{cases} {dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j])(S[i]==T[j] And full foot S in front i individual the Yes Yes Should be word mother Count Small On etc. On T in word mother Count )

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
void solve(){
int n;
string s,t;
cin>>n>>s>>t;
vector<vector<int> >numS(n+1,vector<int>(26)),numT(n+1,vector<int>(26));
for(int i=0;i<n;i++){
numS[i+1]=numS[i];// Direct the entire assignment
numT[i+1]=numT[i];
numS[i+1][s[i]-'a']++;
numT[i+1][t[i]-'a']++;
}
/*for(int i=0;i<26;i++) printf("%d %d\n",numS[i],numT[i]); */
if(numS[n]!=numT[n]){
cout<<-1<<endl;
return ;
}
vector<vector<int> >dp(n+1,vector<int>(n+1,-1e9));
dp=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++){
if(i<n) dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j<n) dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
if(i<=j&&i<n&&j<n&&s[i]==t[j]){
int f=0;
for(int k=0;k<26;k++)
if(numS[i][k]>numT[j][k]) f=1;
if(!f) dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
}
}
cout<<n-dp[n][n]<<endl;//n- The biggest match
}
int main(){
IOS;
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.


https://chowdera.com/2021/08/20210810101454372a.html