101732024-03-28 23:59:41111Regexcpp17Hibás válasz 0/100437ms316880 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Hibás válasz3ms2272 KiB
subtask20/9
3Hibás válasz101ms193944 KiB
4Hibás válasz252ms234900 KiB
5Hibás válasz268ms274932 KiB
6Hibás válasz238ms188548 KiB
7Hibás válasz437ms276160 KiB
8Hibás válasz377ms264344 KiB
subtask30/11
9Elfogadva3ms3072 KiB
10Hibás válasz3ms3436 KiB
11Hibás válasz3ms3528 KiB
12Hibás válasz3ms3516 KiB
13Hibás válasz3ms3716 KiB
14Hibás válasz3ms3932 KiB
subtask40/13
15Hibás válasz3ms4244 KiB
16Hibás válasz3ms4420 KiB
17Hibás válasz3ms4524 KiB
18Hibás válasz3ms4256 KiB
19Hibás válasz3ms4216 KiB
20Hibás válasz3ms4476 KiB
subtask50/24
21Hibás válasz4ms7168 KiB
22Hibás válasz6ms8176 KiB
23Hibás válasz4ms7316 KiB
24Hibás válasz4ms6936 KiB
25Hibás válasz4ms6408 KiB
26Hibás válasz4ms7812 KiB
subtask60/43
27Hibás válasz112ms218884 KiB
28Hibás válasz270ms244988 KiB
29Hibás válasz294ms306144 KiB
30Hibás válasz335ms316880 KiB
31Hibás válasz166ms139200 KiB
32Hibás válasz324ms231780 KiB
33Hibás válasz419ms266556 KiB
34Hibás válasz317ms314260 KiB