10175 2024. 03. 29 00:04:36 111 Regex cpp17 Hibás válasz 0/100 189ms 160968 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],l[i-k][j-k]+k*2);
				}
				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 2080 KiB
2 Elfogadva 3ms 2336 KiB
subtask2 0/9
3 Hibás válasz 50ms 97872 KiB
4 Elfogadva 119ms 118464 KiB
5 Hibás válasz 130ms 138448 KiB
6 Elfogadva 108ms 95308 KiB
7 Hibás válasz 189ms 139392 KiB
8 Hibás válasz 152ms 133580 KiB
subtask3 0/11
9 Elfogadva 3ms 3008 KiB
10 Elfogadva 3ms 3204 KiB
11 Elfogadva 2ms 3200 KiB
12 Elfogadva 3ms 3428 KiB
13 Hibás válasz 3ms 3596 KiB
14 Hibás válasz 3ms 3600 KiB
subtask4 0/13
15 Elfogadva 3ms 3684 KiB
16 Elfogadva 3ms 3956 KiB
17 Hibás válasz 3ms 4092 KiB
18 Elfogadva 3ms 4024 KiB
19 Elfogadva 3ms 4244 KiB
20 Elfogadva 3ms 4492 KiB
subtask5 0/24
21 Elfogadva 4ms 6012 KiB
22 Hibás válasz 4ms 6636 KiB
23 Hibás válasz 4ms 6288 KiB
24 Elfogadva 4ms 5832 KiB
25 Hibás válasz 4ms 5512 KiB
26 Elfogadva 4ms 6500 KiB
subtask6 0/43
27 Elfogadva 54ms 112056 KiB
28 Elfogadva 122ms 125156 KiB
29 Elfogadva 134ms 155724 KiB
30 Elfogadva 152ms 160968 KiB
31 Hibás válasz 83ms 71912 KiB
32 Elfogadva 126ms 118116 KiB
33 Elfogadva 160ms 135724 KiB
34 Hibás válasz 160ms 159556 KiB