#include <bits/stdc++.h>
using namespace std;
const int INF = 1e5;
string a, b;
vector<vector<vector<int>>> dp;
int megold(int a_ind, int b_ind, bool nyitott){
if(a_ind == a.size()){
if(b_ind == b.size()){
return 0;
}
else{
return (b.size() - b_ind) + 3*(!nyitott);
}
}
if(b_ind == b.size()){
return (a.size() - a_ind) + 3*(!nyitott);
}
if(dp[a_ind][b_ind][nyitott] != -1){
return dp[a_ind][b_ind][nyitott];
}
int ret = INF;
if(nyitott){
ret = min(ret, megold(a_ind+1, b_ind, true) + 1);
ret = min(ret, megold(a_ind, b_ind+1, true) + 1);
if(a[a_ind] == b[b_ind]){
ret = min(ret, megold(a_ind+1, b_ind+1, false) + 1);
}
}
else{
ret = min(ret, megold(a_ind+1, b_ind, true) + 4);
ret = min(ret, megold(a_ind, b_ind+1, true) + 4);
if(a[a_ind] == b[b_ind]){
ret = min(ret, megold(a_ind+1, b_ind+1, false) + 1);
}
}
dp[a_ind][b_ind][nyitott] = ret;
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
// dp proba?
int t;
cin >> t;
while(t--){
cin >> a >> b;
dp.assign(a.size(), vector<vector<int>>(b.size(), vector<int>(2, -1)));
cout << megold(0, 0, false) << "\n";
}
/*
for(int k = 0; k < 2; k++){
cout << "\t";
for(int i = 0; i < b.size(); i++){
cout << i << "\t";
}
cout << "\n";
for(int i = 0; i < a.size(); i++){
cout << i << "\t";
for(int j = 0; j < b.size(); j++){
cout << dp[i][j][k] << "\t";
}
cout << "\n";
}
cout << "----------------------\n";
}
*/
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1828 KiB | ||||
2 | Elfogadva | 3ms | 2532 KiB | ||||
subtask2 | 9/9 | ||||||
3 | Elfogadva | 354ms | 338280 KiB | ||||
4 | Elfogadva | 1.08s | 689452 KiB | ||||
5 | Elfogadva | 904ms | 479556 KiB | ||||
6 | Elfogadva | 986ms | 640836 KiB | ||||
7 | Elfogadva | 1.36s | 739004 KiB | ||||
8 | Elfogadva | 1.243s | 815312 KiB | ||||
subtask3 | 11/11 | ||||||
9 | Elfogadva | 3ms | 2916 KiB | ||||
10 | Elfogadva | 3ms | 3016 KiB | ||||
11 | Elfogadva | 3ms | 3140 KiB | ||||
12 | Elfogadva | 2ms | 3248 KiB | ||||
13 | Elfogadva | 3ms | 3428 KiB | ||||
14 | Elfogadva | 2ms | 3516 KiB | ||||
subtask4 | 13/13 | ||||||
15 | Elfogadva | 3ms | 4080 KiB | ||||
16 | Elfogadva | 4ms | 4636 KiB | ||||
17 | Elfogadva | 4ms | 4860 KiB | ||||
18 | Elfogadva | 4ms | 4424 KiB | ||||
19 | Elfogadva | 3ms | 4040 KiB | ||||
20 | Elfogadva | 4ms | 4600 KiB | ||||
subtask5 | 24/24 | ||||||
21 | Elfogadva | 8ms | 8760 KiB | ||||
22 | Elfogadva | 14ms | 10916 KiB | ||||
23 | Elfogadva | 14ms | 10832 KiB | ||||
24 | Elfogadva | 14ms | 11632 KiB | ||||
25 | Elfogadva | 12ms | 9296 KiB | ||||
26 | Elfogadva | 19ms | 14028 KiB | ||||
subtask6 | 0/43 | ||||||
27 | Elfogadva | 437ms | 379580 KiB | ||||
28 | Elfogadva | 1.304s | 669040 KiB | ||||
29 | Elfogadva | 1.376s | 932284 KiB | ||||
30 | Futási hiba | 832ms | 1045956 KiB | ||||
31 | Elfogadva | 778ms | 467868 KiB | ||||
32 | Elfogadva | 987ms | 515452 KiB | ||||
33 | Elfogadva | 1.11s | 462684 KiB | ||||
34 | Elfogadva | 1.455s | 888188 KiB |