167272025-05-11 15:41:29TaxiradioRegexcpp17Hibás válasz 0/100226ms39552 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]);
                if(i != 1 && j!=1 && a[i-2] == b[i-2]){
                    dp1[i][j] = min(dp1[i-1][j-1]+1 , dp1[i][j]);
                }else{
                    dp1[i][j] = min(dp2[i][j] , 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álasz39ms24372 KiB
4Hibás válasz170ms29676 KiB
5Hibás válasz152ms34612 KiB
6Hibás válasz152ms23588 KiB
7Hibás válasz226ms34664 KiB
8Hibás válasz170ms33236 KiB
subtask30/11
9Elfogadva1ms508 KiB
10Hibás válasz1ms508 KiB
11Hibás válasz1ms316 KiB
12Elfogadva1ms564 KiB
13Hibás válasz1ms316 KiB
14Hibás válasz1ms316 KiB
subtask40/13
15Hibás válasz1ms316 KiB
16Hibás válasz1ms316 KiB
17Hibás válasz1ms316 KiB
18Hibás válasz1ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
subtask50/24
21Hibás válasz2ms564 KiB
22Hibás válasz2ms820 KiB
23Hibás válasz2ms756 KiB
24Hibás válasz2ms564 KiB
25Hibás válasz2ms648 KiB
26Hibás válasz2ms684 KiB
subtask60/43
27Hibás válasz43ms27188 KiB
28Hibás válasz156ms30596 KiB
29Hibás válasz162ms38316 KiB
30Hibás válasz216ms39552 KiB
31Hibás válasz111ms17204 KiB
32Hibás válasz125ms28724 KiB
33Hibás válasz193ms33076 KiB
34Hibás válasz193ms39220 KiB