fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const long long INF = 1e16;
  9.  
  10. int N, M;
  11. vector<vector<long long>> W, V;
  12. vector<vector<int>> P, Q;
  13.  
  14. // Hàm tính tổng giá trị của một hàng ô vuông dựa trên mask
  15. long long get_row_cost(int r, int mask, int m_faces) {
  16.     long long cost = 0;
  17.     for (int j = 0; j < m_faces; ++j) {
  18.         if ((mask >> j) & 1) {
  19.             // Giá trị của ô vuông (r, j+1)
  20.             cost += W[r][j + 1] - W[r][j + 2] + V[r][j + 1] - V[r + 1][j + 1];
  21.         }
  22.     }
  23.     return cost;
  24. }
  25.  
  26. // Kiểm tra mask có thỏa mãn ràng buộc dọc P trong hàng r không
  27. bool is_valid_mask(int r, int mask, int m_faces) {
  28.     // Xét các đường dọc p[r][j]
  29.     for (int j = 1; j <= m_faces + 1; ++j) {
  30.         if (P[r][j] == 0) {
  31.             int left_bit = (j == 1) ? 0 : ((mask >> (j - 2)) & 1);
  32.             int right_bit = (j == m_faces + 1) ? 0 : ((mask >> (j - 1)) & 1);
  33.             if (left_bit != right_bit) return false;
  34.         }
  35.     }
  36.     return true;
  37. }
  38.  
  39. // Kiểm tra hai mask liên tiếp có thỏa mãn ràng buộc ngang Q không
  40. bool is_compatible(int r, int old_mask, int new_mask, int m_faces) {
  41.     // q[r][j] nối ô vuông hàng r-1 và hàng r tại cột j
  42.     for (int j = 1; j <= m_faces; ++j) {
  43.         if (Q[r][j] == 0) {
  44.             int top_bit = (old_mask >> (j - 1)) & 1;
  45.             int bot_bit = (new_mask >> (j - 1)) & 1;
  46.             if (top_bit != bot_bit) return false;
  47.         }
  48.     }
  49.     return true;
  50. }
  51.  
  52. int main() {
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(NULL);
  55.  
  56.     int n_in, m_in;
  57.     cin >> n_in >> m_in;
  58.  
  59.     // Đọc dữ liệu thô
  60.     vector<vector<long long>> w_raw(n_in, vector<long long>(m_in + 1));
  61.     for (int i = 1; i < n_in; ++i) for (int j = 1; j <= m_in; ++j) cin >> w_raw[i][j];
  62.     vector<vector<long long>> v_raw(n_in + 1, vector<long long>(m_in));
  63.     for (int i = 1; i <= n_in; ++i) for (int j = 1; j < m_in; ++j) cin >> v_raw[i][j];
  64.     vector<string> p_raw(n_in), q_raw(n_in + 1);
  65.     for (int i = 1; i < n_in; ++i) cin >> p_raw[i];
  66.     for (int i = 1; i <= n_in; ++i) cin >> q_raw[i];
  67.  
  68.     // Quyết định xoay lưới để min(N, M) là chiều cột (M)
  69.     bool swapped = false;
  70.     if (n_in < m_in) {
  71.         swapped = true;
  72.         N = m_in; M = n_in;
  73.         W.assign(N + 1, vector<long long>(M + 1, 0));
  74.         V.assign(N + 1, vector<long long>(M + 1, 0));
  75.         P.assign(N + 1, vector<int>(M + 1, 1));
  76.         Q.assign(N + 1, vector<int>(M + 1, 1));
  77.  
  78.         for(int i=1; i<n_in; ++i) for(int j=1; j<=m_in; ++j) {
  79.             V[j][i] = w_raw[i][j];
  80.             Q[j][i] = p_raw[i][j-1] - '0';
  81.         }
  82.         for(int i=1; i<=n_in; ++i) for(int j=1; j<m_in; ++j) {
  83.             W[j][i] = v_raw[i][j];
  84.             P[j][i] = q_raw[i][j-1] - '0';
  85.         }
  86.     } else {
  87.         N = n_in; M = m_in;
  88.         W = w_raw; V = v_raw;
  89.         P.assign(N, vector<int>(M + 1));
  90.         Q.assign(N + 1, vector<int>(M));
  91.         for(int i=1; i<N; ++i) for(int j=1; j<=M; ++j) P[i][j] = p_raw[i][j-1] - '0';
  92.         for(int i=1; i<=N; ++i) for(int j=1; j<M; ++j) Q[i][j] = q_raw[i][j-1] - '0';
  93.     }
  94.  
  95.     int m_faces = M - 1;
  96.     int n_faces = N - 1;
  97.     if (m_faces <= 0) { cout << 0 << endl; return 0; }
  98.  
  99.     vector<long long> dp(1 << m_faces, -INF);
  100.     dp[0] = 0; // Trạng thái bắt đầu (màu trắng hết)
  101.  
  102.     for (int i = 1; i <= n_faces; ++i) {
  103.         vector<long long> next_dp(1 << m_faces, -INF);
  104.         long long row_costs[1 << 10];
  105.         bool valid_masks[1 << 10];
  106.  
  107.         for (int mask = 0; mask < (1 << m_faces); ++mask) {
  108.             row_costs[mask] = get_row_cost(i, mask, m_faces);
  109.             valid_masks[mask] = is_valid_mask(i, mask, m_faces);
  110.         }
  111.  
  112.         for (int mask = 0; mask < (1 << m_faces); ++mask) {
  113.             if (!valid_masks[mask]) continue;
  114.             for (int prev_mask = 0; prev_mask < (1 << m_faces); ++prev_mask) {
  115.                 if (dp[prev_mask] == -INF) continue;
  116.                 if (is_compatible(i, prev_mask, mask, m_faces)) {
  117.                     next_dp[mask] = max(next_dp[mask], dp[prev_mask] + row_costs[mask]);
  118.                 }
  119.             }
  120.         }
  121.         dp = next_dp;
  122.     }
  123.  
  124.     // Ràng buộc cuối cùng với biên dưới (hàng N)
  125.     long long max_aesthetic = -INF;
  126.     for (int mask = 0; mask < (1 << m_faces); ++mask) {
  127.         if (dp[mask] == -INF) continue;
  128.         bool ok = true;
  129.         for (int j = 1; j <= m_faces; ++j) {
  130.             if (Q[N][j] == 0 && ((mask >> (j - 1)) & 1) != 0) ok = false;
  131.         }
  132.         if (ok) max_aesthetic = max(max_aesthetic, dp[mask]);
  133.     }
  134.  
  135.     if (max_aesthetic < 0) cout << 0 << endl; // Luôn có cách xây rỗng = 0
  136.     else cout << max_aesthetic << endl;
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/HB1ycj
language:
C++14 (gcc 8.3)
created:
2 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!