Guest User

G - Hungry Canadian

a guest
Aug 29th, 2017
172
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.  
  5. #define ll long long int
  6. #define inf 0x3f3f3f3f
  7. #define pb push_back
  8. #define mk make_pair
  9. #define fi first
  10. #define se second
  11. #define ii pair<int, int>
  12. #define all(x) (x).begin(), (x).end()
  13. #define N 37
  14. #define M 10007
  15.  
  16. int a[N][N];
  17. int dp[M][N];
  18. int k;
  19.  
  20. int go(int curr, char prev){
  21.     if(curr>=k)return 0;
  22.     int &ret=dp[curr][prev];
  23.     if(ret!=-1)return ret;
  24.     ret=100000000;
  25.     for(int i=0; i<26; i++){
  26.         ret=min(ret, go(curr+1, i)+a[prev][i]);
  27.     }
  28.     return ret;
  29. }
  30.  
  31. int main(int argc, char const *argv[]){
  32.     ios::sync_with_stdio(false);
  33.     cin >> k;
  34.     memset(dp, -1, sizeof dp);
  35.  
  36.     for(int i=0; i<26; i++){
  37.         for(int j=0; j<26; j++){
  38.             cin >> a[i][j];
  39.         }
  40.     }
  41.  
  42.     int ans=100000000;
  43.     for(int i=0; i<26; i++){
  44.         ans=min(ans, go(1, i));
  45.     }
  46.     cout << ans << endl;
  47.     return 0;
  48. }
RAW Paste Data