4051 2023. 03. 11 00:47:53 zsombor Regex cpp17 Hibás válasz 24/100 126ms 146172 KiB 
#include <iostream>
#include <vector>
using namespace std;

string a, b;
int n, m, Mn;
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 = min(mn[i - 1][j], mn[i][j - 1]);
            if (a[i] != b[j]) { mn[i][j] = Mn; continue; }
            dp[i][j] = Mn + 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, 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 61ms 142888 KiB
2 Elfogadva 50ms 143368 KiB
subtask2 0/9
3 Hibás válasz 71ms 143496 KiB
4 Hibás válasz 105ms 143836 KiB
5 Hibás válasz 105ms 143920 KiB
6 Hibás válasz 105ms 144132 KiB
7 Hibás válasz 104ms 144388 KiB
8 Hibás válasz 112ms 144212 KiB
subtask3 11/11
9 Elfogadva 50ms 144528 KiB
10 Elfogadva 48ms 144616 KiB
11 Elfogadva 61ms 144664 KiB
12 Elfogadva 50ms 145032 KiB
13 Elfogadva 48ms 144956 KiB
14 Elfogadva 61ms 145084 KiB
subtask4 13/13
15 Elfogadva 50ms 145296 KiB
16 Elfogadva 61ms 145636 KiB
17 Elfogadva 61ms 145588 KiB
18 Elfogadva 50ms 145552 KiB
19 Elfogadva 48ms 145896 KiB
20 Elfogadva 48ms 145856 KiB
subtask5 0/24
21 Elfogadva 61ms 145760 KiB
22 Hibás válasz 63ms 145672 KiB
23 Elfogadva 50ms 145824 KiB
24 Hibás válasz 61ms 145776 KiB
25 Hibás válasz 48ms 145796 KiB
26 Hibás válasz 61ms 146048 KiB
subtask6 0/43
27 Elfogadva 74ms 145900 KiB
28 Hibás válasz 97ms 146028 KiB
29 Hibás válasz 97ms 146104 KiB
30 Hibás válasz 126ms 146172 KiB
31 Hibás válasz 79ms 146168 KiB
32 Hibás válasz 108ms 146172 KiB
33 Hibás válasz 126ms 146172 KiB
34 Hibás válasz 101ms 146112 KiB