pastebin

Paste Search Dynamic
Recent pastes
minimize
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m, f[303][303];
  5. char s[303], t[303];
  6.  
  7. void minimize(int &a, int b) {
  8.         if (a > b) a = b;
  9. }
  10.  
  11. int dp(int i, int j) {
  12.         if (j > m) return 0;
  13.        
  14.         int rs = f[i][j];
  15.         if (rs != -1) return rs;
  16.        
  17.         rs = 0x3f;
  18.         for(int k = 1; k <= n; k++) {
  19.                 if (k - 1 > 0 && s[k - 1] == t[j]) minimize(rs, dp(k - 1, j + 1) + abs(k - i) + 1);
  20.                 if (k + 1 <= n && s[k + 1] == t[j]) minimize(rs, dp(k + 1, j + 1) + abs(k - i) + 1);
  21.         }
  22.        
  23.         return (f[i][j] = rs);
  24. }
  25.  
  26. int main() {
  27.         ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  28.        
  29.         cin >> n >> m;
  30.         for(int i = 1; i <= n; i++) {
  31.                 cin >> s[i];
  32.         }
  33.        
  34.         for(int j = 1; j <= m; j++) {
  35.                 cin >> t[j];
  36.         }
  37.        
  38.         int best = 0x3f;
  39.         memset(f, -1, sizeof f);
  40.         for(int i = 1; i <= n; i++) {
  41.                 if (s[i] == t[1]) minimize(best, dp(i, 2));
  42.         }
  43.        
  44.         cout << (best == 0x3f ? -1 : best);
  45. }
Parsed in 0.013 seconds