10174 2024. 03. 29 00:02:47 111 Regex cpp17 Hibás válasz 0/100 148ms 160648 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	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++){
			dp[i][0]=i;
			l[i][0]=i+3;
		}
		for(int i=0;i<=M;i++){
			dp[0][i]=i;
			l[0][i]=i+3;
		}
		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 1828 KiB
2 Elfogadva 3ms 2244 KiB
subtask2 0/9
3 Hibás válasz 57ms 98172 KiB
4 Elfogadva 119ms 118736 KiB
5 Hibás válasz 130ms 139004 KiB
6 Elfogadva 98ms 95932 KiB
7 Hibás válasz 148ms 139892 KiB
8 Hibás válasz 123ms 133984 KiB
subtask3 0/11
9 Elfogadva 2ms 3376 KiB
10 Elfogadva 3ms 3508 KiB
11 Elfogadva 2ms 3588 KiB
12 Elfogadva 3ms 3812 KiB
13 Hibás válasz 3ms 4052 KiB
14 Hibás válasz 3ms 4124 KiB
subtask4 0/13
15 Elfogadva 3ms 4292 KiB
16 Elfogadva 3ms 4232 KiB
17 Hibás válasz 3ms 4520 KiB
18 Elfogadva 3ms 4432 KiB
19 Elfogadva 3ms 4408 KiB
20 Elfogadva 3ms 4424 KiB
subtask5 0/24
21 Elfogadva 3ms 5676 KiB
22 Hibás válasz 4ms 6348 KiB
23 Hibás válasz 4ms 5856 KiB
24 Elfogadva 4ms 5692 KiB
25 Hibás válasz 3ms 5268 KiB
26 Elfogadva 4ms 6000 KiB
subtask6 0/43
27 Elfogadva 52ms 111600 KiB
28 Elfogadva 126ms 124612 KiB
29 Elfogadva 126ms 155540 KiB
30 Elfogadva 141ms 160648 KiB
31 Hibás válasz 71ms 71688 KiB
32 Elfogadva 105ms 117868 KiB
33 Elfogadva 135ms 135336 KiB
34 Hibás válasz 133ms 159172 KiB