4049 2023. 03. 10 23:37:22 zsombor Regex cpp17 Hibás válasz 24/100 280ms 216560 KiB 
#include <iostream>
#include <vector>
using namespace std;

string a, b;
int n, m, I, J, ans;
vector <vector<int>> dp(3e3, vector<int>(3e3, 1e9));
vector <vector<int>> mni(3e3, vector<int>(3e3, 0));
vector <vector<int>> mnj(3e3, vector<int>(3e3, 0));

void solve() {
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = "a" + a;
    b = "a" + b;
    ans = 1e9;
    dp[0][0] = n + m + 3;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            I = (dp[mni[i - 1][j]][mnj[i - 1][j]] < dp[mni[i][j - 1]][mnj[i][j - 1]] ? mni[i - 1][j] : mni[i][j - 1]);
            J = (dp[mni[i - 1][j]][mnj[i - 1][j]] < dp[mni[i][j - 1]][mnj[i][j - 1]] ? mnj[i - 1][j] : mnj[i][j - 1]);
            mni[i][j] = I;
            mnj[i][j] = J;
            if (a[i] != b[j]) continue;
            dp[i][j] = (a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] - 1 : dp[I][J] + 2);
            if (i == n && j == m) dp[i][j] -= 3;
            mni[i][j] = (dp[i][j] < dp[I][J] ? i : I);
            mnj[i][j] = (dp[i][j] < dp[I][J] ? j : J);
        }
    }
    cout << dp[mni[n][m]][mnj[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 71ms 213624 KiB
2 Elfogadva 92ms 213940 KiB
subtask2 0/9
3 Hibás válasz 104ms 214156 KiB
4 Hibás válasz 207ms 214372 KiB
5 Hibás válasz 231ms 214584 KiB
6 Hibás válasz 229ms 214792 KiB
7 Hibás válasz 275ms 214752 KiB
8 Hibás válasz 248ms 214748 KiB
subtask3 11/11
9 Elfogadva 90ms 214740 KiB
10 Elfogadva 90ms 214744 KiB
11 Elfogadva 72ms 214816 KiB
12 Elfogadva 90ms 214740 KiB
13 Elfogadva 90ms 215000 KiB
14 Elfogadva 72ms 215324 KiB
subtask4 13/13
15 Elfogadva 90ms 215644 KiB
16 Elfogadva 92ms 215376 KiB
17 Elfogadva 92ms 215380 KiB
18 Elfogadva 92ms 215452 KiB
19 Elfogadva 72ms 215520 KiB
20 Elfogadva 90ms 215848 KiB
subtask5 0/24
21 Elfogadva 92ms 216056 KiB
22 Hibás válasz 75ms 216248 KiB
23 Elfogadva 92ms 216244 KiB
24 Hibás válasz 75ms 216460 KiB
25 Hibás válasz 92ms 216348 KiB
26 Hibás válasz 75ms 216224 KiB
subtask6 0/43
27 Elfogadva 107ms 216376 KiB
28 Hibás válasz 221ms 216232 KiB
29 Hibás válasz 225ms 216232 KiB
30 Hibás válasz 277ms 216304 KiB
31 Hibás válasz 187ms 216348 KiB
32 Hibás válasz 231ms 216300 KiB
33 Hibás válasz 280ms 216560 KiB
34 Hibás válasz 261ms 216512 KiB