167282025-05-11 15:45:41TaxiradioRegexcpp17Hibás válasz 0/100266ms39676 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

const int lim = 2000000000;

int main() {
	int t;cin >> t; 
    while(t--){
        string a , b; cin >> a >> b;
        int n = a.size() , m = b.size();
        vector<vector<int>> dp1(n+2 , vector<int>(m+2 , lim)) , dp2(n+2 , vector<int>(m+2 , lim));
        dp1[1][1] = 0;
        dp2[1][1] = 3;
        for(int i = 1; i < n+2; i++){
            for(int j = 1; j < m+2; j++){
                dp2[i][j] = min(min(min(dp1[i-1][j]+4 , dp1[i][j-1]+4) , min(dp2[i-1][j]+1 , dp2[i][j-1]+1)), dp2[i][j]);
                dp1[i][j] = min(dp2[i][j] , dp1[i][j]);
                if(i != 1 && j!=1 && a[i-2] == b[i-2]){
                    dp1[i][j] = min(dp1[i-1][j-1]+1 , dp1[i][j]);
                }
            }
        }
        cout << dp1.back().back() << "\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Hibás válasz1ms316 KiB
subtask20/9
3Hibás válasz46ms24380 KiB
4Hibás válasz182ms29504 KiB
5Hibás válasz182ms34452 KiB
6Hibás válasz201ms23576 KiB
7Hibás válasz266ms34660 KiB
8Hibás válasz204ms33240 KiB
subtask30/11
9Elfogadva1ms500 KiB
10Hibás válasz1ms316 KiB
11Hibás válasz1ms316 KiB
12Elfogadva1ms316 KiB
13Hibás válasz1ms316 KiB
14Hibás válasz1ms316 KiB
subtask40/13
15Hibás válasz1ms508 KiB
16Hibás válasz1ms316 KiB
17Hibás válasz1ms500 KiB
18Hibás válasz1ms508 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
subtask50/24
21Hibás válasz2ms564 KiB
22Hibás válasz3ms820 KiB
23Hibás válasz2ms756 KiB
24Hibás válasz2ms568 KiB
25Hibás válasz2ms564 KiB
26Hibás válasz3ms820 KiB
subtask60/43
27Hibás válasz50ms27188 KiB
28Hibás válasz190ms30564 KiB
29Hibás válasz217ms38192 KiB
30Hibás válasz232ms39676 KiB
31Hibás válasz133ms17204 KiB
32Hibás válasz171ms28720 KiB
33Hibás válasz259ms33072 KiB
34Hibás válasz210ms39240 KiB