101752024-03-29 00:04:36111Regexcpp17Hibás válasz 0/100189ms160968 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2080 KiB
2Elfogadva3ms2336 KiB
subtask20/9
3Hibás válasz50ms97872 KiB
4Elfogadva119ms118464 KiB
5Hibás válasz130ms138448 KiB
6Elfogadva108ms95308 KiB
7Hibás válasz189ms139392 KiB
8Hibás válasz152ms133580 KiB
subtask30/11
9Elfogadva3ms3008 KiB
10Elfogadva3ms3204 KiB
11Elfogadva2ms3200 KiB
12Elfogadva3ms3428 KiB
13Hibás válasz3ms3596 KiB
14Hibás válasz3ms3600 KiB
subtask40/13
15Elfogadva3ms3684 KiB
16Elfogadva3ms3956 KiB
17Hibás válasz3ms4092 KiB
18Elfogadva3ms4024 KiB
19Elfogadva3ms4244 KiB
20Elfogadva3ms4492 KiB
subtask50/24
21Elfogadva4ms6012 KiB
22Hibás válasz4ms6636 KiB
23Hibás válasz4ms6288 KiB
24Elfogadva4ms5832 KiB
25Hibás válasz4ms5512 KiB
26Elfogadva4ms6500 KiB
subtask60/43
27Elfogadva54ms112056 KiB
28Elfogadva122ms125156 KiB
29Elfogadva134ms155724 KiB
30Elfogadva152ms160968 KiB
31Hibás válasz83ms71912 KiB
32Elfogadva126ms118116 KiB
33Elfogadva160ms135724 KiB
34Hibás válasz160ms159556 KiB