10177 2024. 03. 29 00:26:00 111 Regex cpp17 Hibás válasz 0/100 134ms 160584 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();
		// N=100,M=100;
		// for(int i=0;i<N;i++)A+='a'+rand()%3;
		// for(int i=0;i<M;i++)B+='a'+rand()%3;
		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);
					break;
				}
				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 1824 KiB
2 Elfogadva 3ms 2208 KiB
subtask2 0/9
3 Hibás válasz 54ms 98084 KiB
4 Elfogadva 105ms 118732 KiB
5 Hibás válasz 112ms 139004 KiB
6 Elfogadva 96ms 95720 KiB
7 Hibás válasz 131ms 139548 KiB
8 Hibás válasz 119ms 133640 KiB
subtask3 0/11
9 Elfogadva 3ms 3052 KiB
10 Elfogadva 3ms 3304 KiB
11 Elfogadva 3ms 3324 KiB
12 Elfogadva 3ms 3324 KiB
13 Hibás válasz 3ms 3332 KiB
14 Hibás válasz 3ms 3424 KiB
subtask4 0/13
15 Elfogadva 3ms 3636 KiB
16 Elfogadva 3ms 3580 KiB
17 Hibás válasz 3ms 3860 KiB
18 Elfogadva 3ms 4148 KiB
19 Elfogadva 3ms 3964 KiB
20 Elfogadva 3ms 4044 KiB
subtask5 0/24
21 Elfogadva 3ms 5544 KiB
22 Hibás válasz 4ms 6228 KiB
23 Hibás válasz 4ms 5624 KiB
24 Elfogadva 4ms 5580 KiB
25 Hibás válasz 3ms 5140 KiB
26 Elfogadva 4ms 5880 KiB
subtask6 0/43
27 Elfogadva 59ms 111472 KiB
28 Elfogadva 112ms 124444 KiB
29 Elfogadva 126ms 154976 KiB
30 Elfogadva 123ms 160584 KiB
31 Hibás válasz 61ms 72032 KiB
32 Elfogadva 92ms 117880 KiB
33 Elfogadva 130ms 135280 KiB
34 Hibás válasz 134ms 159244 KiB