10179 2024. 03. 29 00:40:33 111 Regex cpp17 Elfogadva 100/100 108ms 81760 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);
				if(A[i-1]==B[j-1]){
					dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
				}
				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 1828 KiB
2 Elfogadva 3ms 2172 KiB
subtask2 9/9
3 Elfogadva 34ms 50220 KiB
4 Elfogadva 82ms 60400 KiB
5 Elfogadva 85ms 70712 KiB
6 Elfogadva 76ms 48892 KiB
7 Elfogadva 104ms 70828 KiB
8 Elfogadva 93ms 68156 KiB
subtask3 11/11
9 Elfogadva 3ms 2736 KiB
10 Elfogadva 3ms 2872 KiB
11 Elfogadva 3ms 2948 KiB
12 Elfogadva 3ms 3084 KiB
13 Elfogadva 3ms 3300 KiB
14 Elfogadva 3ms 3524 KiB
subtask4 13/13
15 Elfogadva 3ms 3532 KiB
16 Elfogadva 3ms 3604 KiB
17 Elfogadva 3ms 3552 KiB
18 Elfogadva 3ms 3532 KiB
19 Elfogadva 3ms 3548 KiB
20 Elfogadva 3ms 3516 KiB
subtask5 24/24
21 Elfogadva 3ms 3988 KiB
22 Elfogadva 3ms 4384 KiB
23 Elfogadva 3ms 4144 KiB
24 Elfogadva 3ms 4052 KiB
25 Elfogadva 3ms 3736 KiB
26 Elfogadva 4ms 4176 KiB
subtask6 43/43
27 Elfogadva 37ms 57160 KiB
28 Elfogadva 87ms 63692 KiB
29 Elfogadva 94ms 79020 KiB
30 Elfogadva 108ms 81760 KiB
31 Elfogadva 54ms 37204 KiB
32 Elfogadva 81ms 60260 KiB
33 Elfogadva 104ms 68896 KiB
34 Elfogadva 101ms 80872 KiB