제출 #1336498

#제출 시각아이디문제언어결과실행 시간메모리
1336498Zone_zoneeBajka (COCI20_bajka)C++20
20 / 70
2 ms580 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 310;

int dp[N][N];
vector<int> idxes[30];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    a = '.'+a;
    for(int i = 1; i <= n; ++i) idxes[a[i]-'a'].push_back(i);
    memset(dp, 0x3f, sizeof dp);
    for(int i : idxes[b.front()-'a']) dp[1][i] = 0;
    b = '.'+b;

    for(int i = 2; i <= m; ++i){

        for(int j : idxes[b[i]-'a']){
            int mn = 1e9;

            for(int k : idxes[b[i-1]-'a']){
                if(j == k) continue;
                if(abs(j-k) < abs(j-mn)) mn = k;
                dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(j-k));
            }

            if(mn == 1e9) continue;
            for(int k : idxes[b[i-1]-'a']){
                dp[i][j] = min(dp[i][j], dp[i][k] + abs(j-mn) + 1);
            }
        }
    }
    int res = 1e9;
    for(int i = 1; i <= n; ++i) res = min(res, dp[m][i]);
    cout << (res == 1e9 ? -1 : res) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...