5309 2023. 04. 25 19:01:23 gortomi Regex cpp17 Elfogadva 100/100 189ms 82060 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, INT_MAX));
    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 1828 KiB
2 Elfogadva 3ms 2184 KiB
subtask2 9/9
3 Elfogadva 30ms 50200 KiB
4 Elfogadva 122ms 60596 KiB
5 Elfogadva 142ms 70856 KiB
6 Elfogadva 122ms 49432 KiB
7 Elfogadva 189ms 71728 KiB
8 Elfogadva 165ms 68732 KiB
subtask3 11/11
9 Elfogadva 3ms 3204 KiB
10 Elfogadva 3ms 3284 KiB
11 Elfogadva 3ms 3644 KiB
12 Elfogadva 3ms 3532 KiB
13 Elfogadva 3ms 3720 KiB
14 Elfogadva 3ms 3852 KiB
subtask4 13/13
15 Elfogadva 2ms 3916 KiB
16 Elfogadva 3ms 3932 KiB
17 Elfogadva 3ms 4068 KiB
18 Elfogadva 3ms 3984 KiB
19 Elfogadva 3ms 3972 KiB
20 Elfogadva 3ms 3996 KiB
subtask5 24/24
21 Elfogadva 3ms 4624 KiB
22 Elfogadva 3ms 4820 KiB
23 Elfogadva 4ms 4664 KiB
24 Elfogadva 3ms 4476 KiB
25 Elfogadva 3ms 4432 KiB
26 Elfogadva 4ms 4732 KiB
subtask6 43/43
27 Elfogadva 35ms 57624 KiB
28 Elfogadva 134ms 64076 KiB
29 Elfogadva 137ms 79444 KiB
30 Elfogadva 165ms 82060 KiB
31 Elfogadva 85ms 37604 KiB
32 Elfogadva 123ms 61096 KiB
33 Elfogadva 168ms 69988 KiB
34 Elfogadva 153ms 81856 KiB