当前位置:网站首页>F. Rotating Substrings(dp)

F. Rotating Substrings(dp)

2021-08-10 10:17:47 wx6110fa547fd20

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[1][i],numT[1][i]); */
	if(numS[n]!=numT[n]){
		cout<<-1<<endl;
		return ;
	}
	vector<vector<int> >dp(n+1,vector<int>(n+1,-1e9));
	dp[0][0]=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.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810101454372a.html