4054 2023. 03. 11 10:55:43 zsombor Regex cpp17 Elfogadva 100/100 122ms 145976 KiB 
#include <iostream>
#include <vector>
using namespace std;

string a, b;
int n, m;
vector <vector <int>> dp(3e3, vector <int>(3e3, 1e9));
vector <vector <int>> mn(3e3, vector <int>(3e3, 0));

void solve() {
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = "a" + a;
    b = "a" + b;
    dp[0][0] = n + m + 3;
    for (int i = 0; i <= n; i++) mn[i][0] = dp[0][0];
    for (int j = 0; j <= m; j++) mn[0][j] = dp[0][0];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]);
            if (a[i] != b[j]) continue;
            dp[i][j] = mn[i - 1][j - 1] + 2;
            if (a[i - 1] == b[j - 1]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] - 1);
            if (i == n && j == m) dp[i][j] -= 3;
            mn[i][j] = min(mn[i][j], dp[i][j]);
        }
    }
    cout << mn[n][m] << endl;
}

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) solve();
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 50ms 142892 KiB
2 Elfogadva 48ms 143052 KiB
subtask2 9/9
3 Elfogadva 71ms 143404 KiB
4 Elfogadva 90ms 143740 KiB
5 Elfogadva 104ms 143876 KiB
6 Elfogadva 92ms 143928 KiB
7 Elfogadva 104ms 144248 KiB
8 Elfogadva 111ms 144456 KiB
subtask3 11/11
9 Elfogadva 50ms 144404 KiB
10 Elfogadva 48ms 144420 KiB
11 Elfogadva 61ms 144532 KiB
12 Elfogadva 61ms 144548 KiB
13 Elfogadva 61ms 144800 KiB
14 Elfogadva 61ms 144876 KiB
subtask4 13/13
15 Elfogadva 50ms 144956 KiB
16 Elfogadva 48ms 144876 KiB
17 Elfogadva 61ms 144776 KiB
18 Elfogadva 48ms 144780 KiB
19 Elfogadva 61ms 145108 KiB
20 Elfogadva 63ms 145172 KiB
subtask5 24/24
21 Elfogadva 63ms 145052 KiB
22 Elfogadva 63ms 145260 KiB
23 Elfogadva 63ms 145264 KiB
24 Elfogadva 63ms 145348 KiB
25 Elfogadva 63ms 145484 KiB
26 Elfogadva 63ms 145412 KiB
subtask6 43/43
27 Elfogadva 61ms 145668 KiB
28 Elfogadva 112ms 145660 KiB
29 Elfogadva 111ms 145652 KiB
30 Elfogadva 119ms 145636 KiB
31 Elfogadva 79ms 145828 KiB
32 Elfogadva 104ms 145976 KiB
33 Elfogadva 122ms 145836 KiB
34 Elfogadva 103ms 145836 KiB