5308 2023. 04. 25 18:59:15 gortomi Regex cpp17 Hibás válasz 0/100 196ms 82696 KiB 
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<vector<int> > dp1(n + 1, vector<int>(m + 1)), dp2(n + 1, vector<int>(m + 1));
    for(int i = 0; i <= n; i++)
    {
        dp1[i][m] = n - i + 3;
        dp2[i][m] = n - i;
    }
    for(int i = 0; i <= m; i++)
    {
        dp1[n][i] = m - i + 3;
        dp2[n][i] = m - i;
    }
    dp1[n][m] = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = m - 1; j >= 0; j--)
        {
            if(a[i] == b[j])
            {
                dp1[i][j] = dp1[i + 1][j + 1] + 1;
                dp2[i][j] = dp1[i + 1][j + 1] + 1;
            }
            else dp1[i][j] = min(dp2[i + 1][j] + 4, dp2[i][j + 1] + 4);
            dp2[i][j] = min(dp2[i][j], dp2[i + 1][j] + 1);
            dp2[i][j] = min(dp2[i][j], dp2[i][j + 1] + 1);
        }
    }
    cout << dp1[0][0] << "\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1836 KiB
2 Hibás válasz 3ms 2184 KiB
subtask2 0/9
3 Hibás válasz 30ms 49968 KiB
4 Hibás válasz 123ms 60624 KiB
5 Hibás válasz 142ms 70844 KiB
6 Hibás válasz 146ms 49136 KiB
7 Hibás válasz 165ms 71408 KiB
8 Hibás válasz 142ms 68384 KiB
subtask3 0/11
9 Hibás válasz 3ms 3080 KiB
10 Hibás válasz 3ms 3188 KiB
11 Hibás válasz 3ms 3196 KiB
12 Hibás válasz 3ms 3396 KiB
13 Hibás válasz 3ms 3608 KiB
14 Hibás válasz 3ms 3816 KiB
subtask4 0/13
15 Hibás válasz 3ms 3952 KiB
16 Hibás válasz 3ms 3968 KiB
17 Hibás válasz 3ms 4008 KiB
18 Hibás válasz 3ms 3992 KiB
19 Hibás válasz 3ms 4188 KiB
20 Hibás válasz 3ms 4180 KiB
subtask5 0/24
21 Hibás válasz 3ms 4952 KiB
22 Hibás válasz 4ms 5096 KiB
23 Hibás válasz 4ms 5196 KiB
24 Hibás válasz 4ms 5116 KiB
25 Hibás válasz 3ms 5028 KiB
26 Hibás válasz 4ms 5216 KiB
subtask6 0/43
27 Hibás válasz 39ms 58368 KiB
28 Hibás válasz 156ms 64708 KiB
29 Hibás válasz 158ms 79964 KiB
30 Hibás válasz 194ms 82696 KiB
31 Hibás válasz 86ms 38140 KiB
32 Hibás válasz 143ms 61408 KiB
33 Hibás válasz 196ms 70240 KiB
34 Hibás válasz 177ms 82104 KiB