10178 2024. 03. 29 00:39:23 111 Regex cpp17 Elfogadva 100/100 166ms 161008 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Elfogadva 3ms 2248 KiB
subtask2 9/9
3 Elfogadva 57ms 97868 KiB
4 Elfogadva 126ms 118740 KiB
5 Elfogadva 137ms 138640 KiB
6 Elfogadva 105ms 95524 KiB
7 Elfogadva 158ms 139492 KiB
8 Elfogadva 130ms 133944 KiB
subtask3 11/11
9 Elfogadva 3ms 3132 KiB
10 Elfogadva 3ms 3320 KiB
11 Elfogadva 3ms 3436 KiB
12 Elfogadva 3ms 3636 KiB
13 Elfogadva 3ms 3736 KiB
14 Elfogadva 2ms 3800 KiB
subtask4 13/13
15 Elfogadva 3ms 4036 KiB
16 Elfogadva 3ms 4000 KiB
17 Elfogadva 3ms 4288 KiB
18 Elfogadva 3ms 4404 KiB
19 Elfogadva 3ms 4588 KiB
20 Elfogadva 3ms 4788 KiB
subtask5 24/24
21 Elfogadva 3ms 5900 KiB
22 Elfogadva 4ms 6572 KiB
23 Elfogadva 4ms 6080 KiB
24 Elfogadva 4ms 5808 KiB
25 Elfogadva 3ms 5392 KiB
26 Elfogadva 4ms 6116 KiB
subtask6 43/43
27 Elfogadva 52ms 111716 KiB
28 Elfogadva 119ms 124824 KiB
29 Elfogadva 148ms 155724 KiB
30 Elfogadva 166ms 161008 KiB
31 Elfogadva 75ms 71960 KiB
32 Elfogadva 123ms 118356 KiB
33 Elfogadva 144ms 136080 KiB
34 Elfogadva 141ms 159852 KiB