5374 2023. 04. 26 19:48:04 rmlan Regex cpp14 Hibás válasz 24/100 104ms 83072 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++){
                if(a[i-1]==b[j-1]){
                    //cout << "ok";
                    dp[i][j][0]=min(dp[i-1][j-1][0], dp[i-1][j-1][1])+1;
                    dp[i][j][1]=dp[i-1][j-1][1]+2;
                    dp[i][j][1]=min(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);
                }else{

                    dp[i][j][0]=1e5;
                    dp[i][j][1]=dp[i-1][j-1][1]+2;
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][0]+5);
                    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);
                    dp[i][j][1]=min(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);
                }
            //cout << dp[i][j][0] << " "<<dp[i][j][1] << "    :" << i << " " << j << endl;
            }//cout << endl;
        }
        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 1816 KiB
2 Elfogadva 3ms 2080 KiB
subtask2 0/9
3 Elfogadva 28ms 50256 KiB
4 Elfogadva 78ms 60592 KiB
5 Hibás válasz 82ms 70920 KiB
6 Hibás válasz 70ms 49376 KiB
7 Elfogadva 97ms 71400 KiB
8 Elfogadva 87ms 68468 KiB
subtask3 11/11
9 Elfogadva 3ms 3204 KiB
10 Elfogadva 2ms 3296 KiB
11 Elfogadva 3ms 3280 KiB
12 Elfogadva 2ms 3252 KiB
13 Elfogadva 3ms 3384 KiB
14 Elfogadva 3ms 3592 KiB
subtask4 13/13
15 Elfogadva 3ms 3720 KiB
16 Elfogadva 3ms 3984 KiB
17 Elfogadva 3ms 4204 KiB
18 Elfogadva 3ms 4520 KiB
19 Elfogadva 3ms 4468 KiB
20 Elfogadva 3ms 4372 KiB
subtask5 0/24
21 Elfogadva 3ms 5132 KiB
22 Elfogadva 4ms 5272 KiB
23 Elfogadva 3ms 5152 KiB
24 Hibás válasz 4ms 5084 KiB
25 Elfogadva 3ms 5064 KiB
26 Elfogadva 4ms 5632 KiB
subtask6 0/43
27 Elfogadva 34ms 58408 KiB
28 Hibás válasz 82ms 65012 KiB
29 Hibás válasz 89ms 80328 KiB
30 Elfogadva 101ms 83072 KiB
31 Hibás válasz 54ms 38568 KiB
32 Hibás válasz 82ms 61620 KiB
33 Elfogadva 100ms 70288 KiB
34 Hibás válasz 104ms 82224 KiB