fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. const ll INF = 1e16; 
  9.  
  10. int n;
  11. char board[13][13];
  12. int weight[13][13];
  13. ll dp[1 << 24]; 
  14.  
  15. int main() {
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(NULL);
  18.  
  19.     cin >> n;
  20.  
  21.     for (int i = 0; i < n; i++) cin >> board[i];
  22.     for (int i = 0; i < n; i++)
  23.         for (int j = 0; j < n; j++) cin >> weight[i][j];
  24.  
  25.     int max_mask = 1 << (2 * n);
  26.     fill(dp, dp + max_mask, INF);
  27.  
  28.     int start_mask = ((1 << n) - 1) << n;
  29.     dp[start_mask] = 0;
  30.  
  31.  
  32.     for (int mask = start_mask; mask >= 0; mask--) {
  33.         if (dp[mask] >= INF) continue;
  34.         if (__builtin_popcount(mask) != n) continue;
  35.  
  36.         int rs[13], cs[13], bits[13];
  37.         int cnt = 0;
  38.         int r = 0, c = 0;
  39.  
  40.         for (int i = 2 * n - 1; i > 0; i--) {
  41.             if (((mask >> i) & 1) && !((mask >> (i - 1)) & 1)) {
  42.                 rs[cnt] = r;
  43.                 cs[cnt] = c;
  44.                 bits[cnt] = i;
  45.                 cnt++;
  46.             }
  47.             if ((mask >> i) & 1) c++; else r++;
  48.         }
  49.  
  50.         for (int i = 0; i < cnt; i++) {
  51.             int r1 = rs[i], c1 = cs[i], b1 = bits[i];
  52.             int mask_after_i = mask ^ (3 << (b1 - 1)); 
  53.  
  54.             if (dp[mask_after_i] > dp[mask] + weight[r1][c1]) {
  55.                 dp[mask_after_i] = dp[mask] + weight[r1][c1];
  56.             }
  57.  
  58.             for (int j = i + 1; j < cnt; j++) {
  59.                 int r2 = rs[j], c2 = cs[j], b2 = bits[j];
  60.                 if (board[r1][c1] != board[r2][c2]) {
  61.                     int mask_after_pair = mask_after_i ^ (3 << (b2 - 1));
  62.                     ll cost = abs(weight[r1][c1] - weight[r2][c2]);
  63.                     if (dp[mask_after_pair] > dp[mask] + cost) {
  64.                         dp[mask_after_pair] = dp[mask] + cost;
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.  
  71.     cout << dp[(1 << n) - 1] << endl;
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/txqVRi
language:
C++14 (gcc 8.3)
created:
5 hours 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!