Fshl0

Moortal Cowmbat

Jun 2nd, 2021
775
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const ll N = 1e5 + 9;
  7. const ll Alpha = 30;
  8. const ll INF = 1e17;
  9.  
  10. ll dp[N][Alpha], A[Alpha][Alpha], dist[Alpha][Alpha], prefixDist[N][Alpha], minDP[N];
  11. ll n, m, k;
  12. string s;
  13.  
  14. int main () {
  15.     freopen ("cowmbat.in", "r", stdin);
  16.     freopen ("cowmbat.out", "w", stdout);
  17.     cin >> n >> m >> k >> s;
  18.     for (ll i = 0; i < m; i++)
  19.         for (ll j = 0; j < m; j++)
  20.             cin >> A[i][j];
  21.     for (ll i = 0; i < m; i++)
  22.         for (ll j = 0; j < m; j++)
  23.             dist[i][j] = A[i][j];
  24.     for (ll k = 0; k < m; k++)
  25.         for (ll i = 0; i < m; i++)
  26.             for (ll j = 0; j < m; j++)
  27.                 dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]);
  28.     for (ll j = 0; j < m; j++)
  29.         prefixDist[0][j] = dist[s[0] - 'a'][j];
  30.     for (ll i = 1; i < n; i++)
  31.         for (ll j = 0; j < m; j++)
  32.             prefixDist[i][j] = prefixDist[i - 1][j] + dist[s[i] - 'a'][j];
  33.     for (ll i = 0; i < n; i++)
  34.         minDP[i] = INF;
  35.     for (ll j = 0; j < m; j++) {
  36.         dp[k - 1][j] = prefixDist[k - 1][j];
  37.         minDP[k - 1] = min (minDP[k - 1], dp[k - 1][j]);
  38.     }
  39.     for (ll i = k; i < n; i++) {
  40.         for (ll j = 0; j < m; j++) {
  41.             dp[i][j] = dp[i - 1][j] + dist[s[i] - 'a'][j];
  42.             if (minDP[i - k] != INF)
  43.                 dp[i][j] = min (dp[i][j], prefixDist[i][j] - prefixDist[i - k][j] + minDP[i - k]);
  44.             minDP[i] = min (minDP[i], dp[i][j]);
  45.         }
  46.     }
  47.     cout << minDP[n - 1] << "\n";
  48.     return 0;
  49. }
  50.  
RAW Paste Data