fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxN = 1e5 + 5;
  6. const int INF = 1e9 + 5;
  7.  
  8. int n, m, k;
  9. string s;
  10. int dis[27][27], pre[27][maxN], f[27][maxN];
  11. int ans = INF;
  12.  
  13. int dp(int pos, int ne){
  14.     if (pos > n) return 0;
  15.     int &res = f[ne][pos];
  16.     if (res != -1) return res;
  17.     res = INF;
  18.     res = min(res, dp(pos+1, ne) + dis[s[pos] - 'a' + 1][ne]);
  19.     if (pos + k - 1 <= n){
  20.         for (int i = 1; i <= m; ++i){
  21.             res = min(res, dp(pos+k, i) + pre[i][pos+k-1] - pre[i][pos-1]);
  22.         }
  23.     }
  24.     return res;
  25. }
  26.  
  27. int main(){
  28.     ios_base::sync_with_stdio(0);
  29.     cin.tie(0);
  30.     if (fopen("cowmbat.in", "r")){
  31.         freopen("cowmbat.in", "r", stdin);
  32.         freopen("cowmbat.out", "w", stdout);
  33.     }
  34.     cin >> n >> m >> k;
  35.     cin >> s; s = " " + s;
  36.     for (int i = 1; i <= m; ++i){
  37.         for (int j = 1; j <= m; ++j){
  38.             cin >> dis[i][j];
  39.         }
  40.     }
  41.     for (int k = 1; k <= m; ++k){
  42.         for (int i = 1; i <= m; ++i){
  43.             for (int j = 1; j <= m; ++j){
  44.                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  45.             }
  46.         }
  47.     }
  48.     for (int i = 1; i <= m; ++i){
  49.         for (int j = 1; j <= n; ++j){
  50.             pre[i][j] = pre[i][j-1] + dis[s[j] - 'a' + 1][i];
  51.         }
  52.     }
  53.     memset(f, -1, sizeof(f));
  54.     for (int i = 1; i <= m; ++i){
  55.         ans = min(ans, dp(k+1, i) + pre[i][k]);
  56.     }
  57.     cout << ans;
  58.  
  59.     return 0;
  60. }
Success #stdin #stdout 0.01s 15556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000005
https://ideone.com/R3HlBV
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!