5375 2023. 04. 26 20:12:37 rmlan Regex cpp14 Hibás válasz 24/100 93ms 82612 KiB 
#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        string a,b;
        cin >> a >> b;
        if(a.length() < b.length()) swap(a,b);
        int dp[a.length()+1][b.length()+1][2];
        dp[0][0][0]=0;
        dp[0][0][1]=3;
        for(int i = 1; i <= a.length(); i++){dp[i][0][1]=i+3; dp[i][0][0]=1e5;}
        for(int i = 1; i <= b.length(); i++){dp[0][i][1]=i+3; dp[0][i][0]=1e5;}
        for(int i = 1; i <= a.length(); i++){
            for(int j = 1; j <= b.length(); j++){


                dp[i][j][1]=dp[i-1][j][1]+1;
                dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][1]+1);
                if(a[i-1]==b[j-1]){
                    dp[i][j][0]=min(dp[i-1][j-1][0], dp[i-1][j-1][1])+1;
                }else{
                    dp[i][j][0]=1e5;

                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][0]+4);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][0]+4);

                }

            }
        }
        cout << min(dp[a.length()][b.length()][0], dp[a.length()][b.length()][1]) << endl;
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Elfogadva 3ms 2028 KiB
subtask2 0/9
3 Elfogadva 32ms 50212 KiB
4 Elfogadva 74ms 60520 KiB
5 Hibás válasz 78ms 70588 KiB
6 Hibás válasz 64ms 48872 KiB
7 Elfogadva 93ms 70944 KiB
8 Elfogadva 83ms 68276 KiB
subtask3 11/11
9 Elfogadva 3ms 3080 KiB
10 Elfogadva 3ms 3272 KiB
11 Elfogadva 2ms 3396 KiB
12 Elfogadva 2ms 3424 KiB
13 Elfogadva 3ms 3424 KiB
14 Elfogadva 2ms 3548 KiB
subtask4 13/13
15 Elfogadva 3ms 3956 KiB
16 Elfogadva 3ms 3796 KiB
17 Elfogadva 3ms 3700 KiB
18 Elfogadva 3ms 3804 KiB
19 Elfogadva 3ms 3764 KiB
20 Elfogadva 3ms 4076 KiB
subtask5 0/24
21 Elfogadva 3ms 4608 KiB
22 Elfogadva 4ms 5132 KiB
23 Elfogadva 3ms 5012 KiB
24 Hibás válasz 3ms 4948 KiB
25 Elfogadva 3ms 4608 KiB
26 Elfogadva 4ms 5056 KiB
subtask6 0/43
27 Elfogadva 32ms 57876 KiB
28 Hibás válasz 74ms 64728 KiB
29 Hibás válasz 87ms 79960 KiB
30 Elfogadva 93ms 82612 KiB
31 Hibás válasz 46ms 38116 KiB
32 Hibás válasz 68ms 61188 KiB
33 Elfogadva 89ms 69892 KiB
34 Hibás válasz 86ms 81868 KiB