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