5345 2023. 04. 26 10:02:07 sztomi Regex cpp11 Hibás válasz 0/100 1.368s 1045884 KiB 
#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;
        }
    }
    if(b_ind == b.size()){
        return (a.size() - a_ind) + 3;
    }

    if(dp[a_ind][b_ind][nyitott] != -1){
        return dp[a_ind][b_ind][nyitott];
    }

    int ret = INF;
    // lehet egyutt haladni
    if(a[a_ind] == b[b_ind]){
        // ha nincs nyitva akkor sztem nincs ertelme kinyitni egyet
        if(!nyitott){
            ret = min(ret, megold(a_ind+1, b_ind+1, false) + 1);
        }
        else{
            // nyitva tartjuk
            ret = min(ret, megold(a_ind+1, b_ind, true) + 1);
            ret = min(ret, megold(a_ind, b_ind+1, true) + 1);
            // bezarjuk
            ret = min(ret, megold(a_ind+1, b_ind+1, true) + 1);
        }
    }
    else{
        if(!nyitott){
            // nyitunk egy ujat
            ret = min(ret, megold(a_ind+1, b_ind, true) + 1 + 3);
            ret = min(ret, megold(a_ind, b_ind+1, true) + 1 + 3);
        }
        else{
            ret = min(ret, megold(a_ind+1, b_ind, true) + 1);
            ret = min(ret, megold(a_ind, b_ind+1, true) + 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, 0) << "\n";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Hibás válasz 3ms 2372 KiB
subtask2 0/9
3 Hibás válasz 379ms 337600 KiB
4 Hibás válasz 1.118s 689240 KiB
5 Hibás válasz 916ms 479576 KiB
6 Hibás válasz 1.014s 640800 KiB
7 Hibás válasz 1.299s 738988 KiB
8 Hibás válasz 1.286s 815448 KiB
subtask3 0/11
9 Elfogadva 3ms 3320 KiB
10 Elfogadva 3ms 3308 KiB
11 Hibás válasz 3ms 3292 KiB
12 Hibás válasz 3ms 3300 KiB
13 Hibás válasz 3ms 3424 KiB
14 Hibás válasz 3ms 3656 KiB
subtask4 0/13
15 Hibás válasz 3ms 4536 KiB
16 Hibás válasz 4ms 5108 KiB
17 Hibás válasz 4ms 5468 KiB
18 Hibás válasz 4ms 5264 KiB
19 Hibás válasz 3ms 4632 KiB
20 Hibás válasz 4ms 5400 KiB
subtask5 0/24
21 Hibás válasz 7ms 9524 KiB
22 Hibás válasz 10ms 11796 KiB
23 Hibás válasz 13ms 11760 KiB
24 Hibás válasz 14ms 12416 KiB
25 Hibás válasz 12ms 9996 KiB
26 Hibás válasz 17ms 14396 KiB
subtask6 0/43
27 Hibás válasz 391ms 379924 KiB
28 Hibás válasz 1.246s 669124 KiB
29 Hibás válasz 1.296s 931828 KiB
30 Futási hiba 824ms 1045884 KiB
31 Hibás válasz 745ms 467940 KiB
32 Hibás válasz 876ms 515520 KiB
33 Hibás válasz 1.103s 462616 KiB
34 Hibás válasz 1.368s 888000 KiB