10173 2024. 03. 28 23:59:41 111 Regex cpp17 Hibás válasz 0/100 437ms 316880 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],a[N+1][M+1],b[N+1][M+1];
		memset(dp,0,sizeof(dp));
		memset(l,0,sizeof(l));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int i=1;i<=N;i++){
			for(int j=1;j<=M;j++){
				l[i][j]=i+j-1-min(i==1?j:dp[i-1][j],j==1?i:dp[i][j-1]);
				l[i][j]=max(l[i][j],max(l[i-1][j],l[i][j-1]));
				a[i][j]=i+j-1-(i==1?j:dp[i-1][j]);
				b[i][j]=i+j-1-(j==1?i:dp[i][j-1]);
				dp[i][j]=i+j+3-l[i][j];
				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);
				}
				// 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 Hibás válasz 3ms 2272 KiB
subtask2 0/9
3 Hibás válasz 101ms 193944 KiB
4 Hibás válasz 252ms 234900 KiB
5 Hibás válasz 268ms 274932 KiB
6 Hibás válasz 238ms 188548 KiB
7 Hibás válasz 437ms 276160 KiB
8 Hibás válasz 377ms 264344 KiB
subtask3 0/11
9 Elfogadva 3ms 3072 KiB
10 Hibás válasz 3ms 3436 KiB
11 Hibás válasz 3ms 3528 KiB
12 Hibás válasz 3ms 3516 KiB
13 Hibás válasz 3ms 3716 KiB
14 Hibás válasz 3ms 3932 KiB
subtask4 0/13
15 Hibás válasz 3ms 4244 KiB
16 Hibás válasz 3ms 4420 KiB
17 Hibás válasz 3ms 4524 KiB
18 Hibás válasz 3ms 4256 KiB
19 Hibás válasz 3ms 4216 KiB
20 Hibás válasz 3ms 4476 KiB
subtask5 0/24
21 Hibás válasz 4ms 7168 KiB
22 Hibás válasz 6ms 8176 KiB
23 Hibás válasz 4ms 7316 KiB
24 Hibás válasz 4ms 6936 KiB
25 Hibás válasz 4ms 6408 KiB
26 Hibás válasz 4ms 7812 KiB
subtask6 0/43
27 Hibás válasz 112ms 218884 KiB
28 Hibás válasz 270ms 244988 KiB
29 Hibás válasz 294ms 306144 KiB
30 Hibás válasz 335ms 316880 KiB
31 Hibás válasz 166ms 139200 KiB
32 Hibás válasz 324ms 231780 KiB
33 Hibás válasz 419ms 266556 KiB
34 Hibás válasz 317ms 314260 KiB