10176 2024. 03. 29 00:18:07 111 Regex cpp17 Időlimit túllépés 0/100 1.603s 76284 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);
				}
				l[i][j]=min(l[i][j],dp[i][j]+3);
				// cout<<setw(4)<<i<<' '<<j<<' '<<dp[i][j]<<' '<<l[i][j]<<'\n';
				int x=1e9;
				for(int ii=0;ii<i;ii++){
					for(int jj=0;jj<j;jj++){
						x=min(x,l[ii][jj]+i+j-ii-jj);
					}
				}
				l[i][j]=min(l[i][j],x);
			}
		}
		cout<<dp[N][M]<<'\n';
	}
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2104 KiB
2 Elfogadva 14ms 2500 KiB
subtask2 0/9
3 Időlimit túllépés 1.603s 49780 KiB
4 Időlimit túllépés 1.564s 41956 KiB
5 Időlimit túllépés 1.539s 70120 KiB
6 Időlimit túllépés 1.569s 46864 KiB
7 Időlimit túllépés 1.56s 69700 KiB
8 Időlimit túllépés 1.555s 53192 KiB
subtask3 0/11
9 Elfogadva 3ms 3276 KiB
10 Elfogadva 3ms 3496 KiB
11 Elfogadva 3ms 3708 KiB
12 Elfogadva 3ms 3776 KiB
13 Hibás válasz 3ms 3912 KiB
14 Hibás válasz 3ms 3924 KiB
subtask4 0/13
15 Elfogadva 14ms 4268 KiB
16 Elfogadva 52ms 4480 KiB
17 Hibás válasz 54ms 4764 KiB
18 Elfogadva 34ms 4628 KiB
19 Elfogadva 20ms 4608 KiB
20 Elfogadva 37ms 4656 KiB
subtask5 0/24
21 Elfogadva 800ms 6172 KiB
22 Időlimit túllépés 1.575s 5068 KiB
23 Időlimit túllépés 1.56s 4868 KiB
24 Időlimit túllépés 1.58s 4896 KiB
25 Hibás válasz 989ms 5828 KiB
26 Időlimit túllépés 1.562s 5020 KiB
subtask6 0/43
27 Időlimit túllépés 1.583s 58032 KiB
28 Időlimit túllépés 1.564s 48808 KiB
29 Időlimit túllépés 1.572s 61644 KiB
30 Időlimit túllépés 1.56s 76284 KiB
31 Időlimit túllépés 1.575s 37832 KiB
32 Időlimit túllépés 1.6s 20512 KiB
33 Időlimit túllépés 1.58s 69700 KiB
34 Időlimit túllépés 1.569s 68384 KiB