Guest User

Untitled

a guest
Dec 14th, 2017
261
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1000 + 13;
  8. const int M = 1 << 12;
  9. const int INF = int(1e9);
  10.  
  11. int dp[N][4][M];
  12. int n;
  13. int a[4];
  14. string f[4];
  15.  
  16. int main() {
  17.     cin >> n;
  18.     forn(i, 4)
  19.         cin >> a[i];
  20.     forn(i, 4){
  21.         cin >> f[i];
  22.         f[i] += "....";
  23.     }
  24.    
  25.     n += 4;
  26.    
  27.     forn(i, n + 1) forn(j, 4) forn(k, M) dp[i][j][k] = INF;
  28.     dp[2][3][0] = 0;
  29.    
  30.     forn(i, n) forn(j, 4) forn(mask, M){
  31.         int st = i * 4 + j - 11;
  32.         int ni = st / 4;
  33.         int nj = st % 4;
  34.        
  35.         if (st < 0)
  36.             continue;
  37.        
  38.         if (n - ni >= 4 && nj == 0){
  39.             dp[i + 1][3][M - 1] = min(dp[i + 1][3][M - 1], dp[i][j][mask] + a[3]);
  40.         }
  41.        
  42.         if ((mask & 1) || f[nj][ni] == '.'){
  43.             int _ni = (i * 4 + j + 1) / 4;
  44.             int _nj = (i * 4 + j + 1) % 4;
  45.            
  46.             dp[_ni][_nj][mask >> 1] = min(dp[_ni][_nj][mask >> 1], dp[i][j][mask]);
  47.         }
  48.        
  49.         for (int t = 1; t <= min(min(n - ni, 4 - nj), 3); ++t){
  50.             int nmask = mask;
  51.             int len = (1 << t) - 1;
  52.             forn(pos, t)
  53.                 nmask |= (len << (4 * pos));
  54.            
  55.             dp[i][j][nmask] = min(dp[i][j][nmask], dp[i][j][mask] + a[t - 1]);
  56.         }
  57.     }
  58.    
  59.     printf("%d\n", dp[n][0][0]);
  60. }
RAW Paste Data