제출 #1333425

#제출 시각아이디문제언어결과실행 시간메모리
1333425ahmetlbktd4Bajka (COCI20_bajka)C++20
70 / 70
101 ms764 KiB
#include "bits/stdc++.h"
using namespace std;

const int N = 301;
const int inf = 1e9;

int  dp[N][N];

int main(){
    int n,m;
    cin >> n >> m;
    string s,s1;
    cin >> s;
    cin >> s1;
    for (int i = 0;i < n;i++){
        for (int j = 0;j <= m;j++){
            dp[i][j] = inf;
        }
    }
    for (int i = 0;i < n;i++){
        dp[i][m] = 0;
    }
    for (int b = m-1;b >= 0;b--){
        for (int a = 0;a < n;a++){
            for (int i = 0;i < n;i++){
                if (s[i]^s[a])
                continue;
                for (int j = -1;j < 2;j++){
                    if (!j)
                    continue;
                    if (i+j < 0 || i+j >= n)
                    continue;
                    if (s[i+j] ^ s1[b])
                    continue;
                    dp[a][b] = min(dp[a][b],dp[i+j][b+1]+abs(i-a)+1);
                }
            }
        }
    }
    int p=inf;
    for (int i = 0;i < n;i++){
        if (s[i] == s1[0])
        p = min(p,dp[i][1]);
    }
    if (p >= inf)
    p=-1;
    cout << p << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...