101782024-03-29 00:39:23111Regexcpp17Elfogadva 100/100166ms161008 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T=-1;
	cin>>T;
	while(T--){
		string A,B;
		cin>>A>>B;
		int N=A.size(),M=B.size();
		int dp[N+1][M+1],l[N+1][M+1];
		for(int i=0;i<=N;i++){
			l[i][0]=dp[i][0]=i+3;
		}
		for(int i=0;i<=M;i++){
			l[0][i]=dp[0][i]=i+3;
		}
		dp[0][0]=0;
		for(int i=1;i<=N;i++){
			for(int j=1;j<=M;j++){
				l[i][j]=dp[i][j]=min(l[i-1][j]+1,l[i][j-1]+1);
				int k=0;
				while(k<i&&k<j&&A[i-k-1]==B[j-k-1]){
					k++;
					dp[i][j]=min(dp[i][j],dp[i-k][j-k]+k);
				}
				l[i][j]=min(l[i][j],dp[i][j]+3);
				// cout<<setw(4)<<i<<' '<<j<<' '<<dp[i][j]<<' '<<l[i][j]<<'\n';
			}
		}
		cout<<dp[N][M]<<'\n';
	}
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Elfogadva3ms2248 KiB
subtask29/9
3Elfogadva57ms97868 KiB
4Elfogadva126ms118740 KiB
5Elfogadva137ms138640 KiB
6Elfogadva105ms95524 KiB
7Elfogadva158ms139492 KiB
8Elfogadva130ms133944 KiB
subtask311/11
9Elfogadva3ms3132 KiB
10Elfogadva3ms3320 KiB
11Elfogadva3ms3436 KiB
12Elfogadva3ms3636 KiB
13Elfogadva3ms3736 KiB
14Elfogadva2ms3800 KiB
subtask413/13
15Elfogadva3ms4036 KiB
16Elfogadva3ms4000 KiB
17Elfogadva3ms4288 KiB
18Elfogadva3ms4404 KiB
19Elfogadva3ms4588 KiB
20Elfogadva3ms4788 KiB
subtask524/24
21Elfogadva3ms5900 KiB
22Elfogadva4ms6572 KiB
23Elfogadva4ms6080 KiB
24Elfogadva4ms5808 KiB
25Elfogadva3ms5392 KiB
26Elfogadva4ms6116 KiB
subtask643/43
27Elfogadva52ms111716 KiB
28Elfogadva119ms124824 KiB
29Elfogadva148ms155724 KiB
30Elfogadva166ms161008 KiB
31Elfogadva75ms71960 KiB
32Elfogadva123ms118356 KiB
33Elfogadva144ms136080 KiB
34Elfogadva141ms159852 KiB