fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <tuple>
  6.  
  7. using namespace std;
  8.  
  9. // Định nghĩa kiểu dữ liệu cho key của DP: (x1, y1, z1, x2, y2, z2)
  10. using State = tuple<int, int, int, int, int, int>;
  11.  
  12. // Khai báo dynamic vectors cho Status và PrefixSum, sử dụng 1-based indexing
  13. vector<vector<vector<int>>> Status;
  14. vector<vector<vector<int>>> PrefixSum;
  15.  
  16. // Sử dụng map cho Memoization (DP table)
  17. map<State, int> DP;
  18.  
  19. int X, Y, Z;
  20.  
  21. /**
  22.  * @brief Tính số khối '1' trong khối con [x1, y1, z1] đến [x2, y2, z2] (1-based index)
  23.  */
  24. int count_ones(int x1, int y1, int z1, int x2, int y2, int z2) {
  25.     if (x1 > x2 || y1 > y2 || z1 > z2) return 0;
  26.  
  27.     // Sử dụng PrefixSum 3D với nguyên tắc loại trừ-bao hàm
  28.     int res = PrefixSum[x2][y2][z2];
  29.  
  30.     // 1 lần trừ
  31.     res -= PrefixSum[x1-1][y2][z2] + PrefixSum[x2][y1-1][z2] + PrefixSum[x2][y2][z1-1];
  32.  
  33.     // 2 lần trừ (cần cộng lại)
  34.     res += PrefixSum[x1-1][y1-1][z2] + PrefixSum[x1-1][y2][z1-1] + PrefixSum[x2][y1-1][z1-1];
  35.  
  36.     // 3 lần trừ (cần trừ đi)
  37.     res -= PrefixSum[x1-1][y1-1][z1-1];
  38.  
  39.     return res;
  40. }
  41.  
  42. /**
  43.  * @brief Hàm Quy hoạch động (6D DP) tìm chi phí tối thiểu để phủ khối con.
  44.  */
  45. int solve(int x1, int y1, int z1, int x2, int y2, int z2) {
  46.     // 1. Trường hợp Cơ sở: Khối không có khối 1 nào
  47.     if (count_ones(x1, y1, z1, x2, y2, z2) == 0) {
  48.         return 0;
  49.     }
  50.  
  51.     // 2. Memoization
  52.     State current_state = {x1, y1, z1, x2, y2, z2};
  53.     if (DP.count(current_state)) {
  54.         return DP[current_state];
  55.     }
  56.  
  57.     // 3. Tính Chi phí Tối thiểu
  58.  
  59.     int dx = x2 - x1 + 1;
  60.     int dy = y2 - y1 + 1;
  61.     int dz = z2 - z1 + 1;
  62.  
  63.     // Lựa chọn 1: Phủ bằng một khối (Single Cover)
  64.     // Chi phí = min(dx, dy, dz)
  65.     int min_cost = min({dx, dy, dz});
  66.  
  67.     // Lựa chọn 2: Tách (Split)
  68.  
  69.     // Tách dọc theo X
  70.     for (int x = x1; x < x2; ++x) {
  71.         // Tách thành [x1..x] và [x+1..x2]
  72.         min_cost = min(min_cost, solve(x1, y1, z1, x, y2, z2) + solve(x + 1, y1, z1, x2, y2, z2));
  73.     }
  74.  
  75.     // Tách dọc theo Y
  76.     for (int y = y1; y < y2; ++y) {
  77.         // Tách thành [y1..y] và [y+1..y2]
  78.         min_cost = min(min_cost, solve(x1, y1, z1, x2, y, z2) + solve(x1, y + 1, z1, x2, y2, z2));
  79.     }
  80.  
  81.     // Tách dọc theo Z
  82.     for (int z = z1; z < z2; ++z) {
  83.         // Tách thành [z1..z] và [z+1..z2]
  84.         min_cost = min(min_cost, solve(x1, y1, z1, x2, y2, z) + solve(x1, y1, z + 1, x2, y2, z2));
  85.     }
  86.  
  87.     // Lưu kết quả và trả về
  88.     return DP[current_state] = min_cost;
  89. }
  90.  
  91. void solve_test_case() {
  92.     if (!(cin >> X >> Y >> Z)) return;
  93.  
  94.     // Reset DP map
  95.     DP.clear();
  96.  
  97.     // Khởi tạo dynamic vectors với kích thước X+1, Y+1, Z+1 cho 1-based indexing
  98.     Status.assign(X + 1, vector<vector<int>>(Y + 1, vector<int>(Z + 1, 0)));
  99.     PrefixSum.assign(X + 1, vector<vector<int>>(Y + 1, vector<int>(Z + 1, 0)));
  100.  
  101.     // Đọc Input và xây dựng PrefixSum
  102.     for (int k = 1; k <= X; ++k) { // X-coordinate (Ma trận k-th)
  103.         for (int i = 1; i <= Y; ++i) { // Y-coordinate (Hàng i-th)
  104.             for (int j = 1; j <= Z; ++j) { // Z-coordinate (Cột j-th)
  105.                 char status_char;
  106.                 if (!(cin >> status_char)) return;
  107.                 Status[k][i][j] = status_char - '0';
  108.  
  109.                 // Tính PrefixSum 3D
  110.                 PrefixSum[k][i][j] = Status[k][i][j]
  111.                                     - PrefixSum[k-1][i-1][j-1]
  112.                                     + PrefixSum[k-1][i][j] + PrefixSum[k][i-1][j] + PrefixSum[k][i][j-1]
  113.                                     - PrefixSum[k-1][i-1][j] - PrefixSum[k-1][i][j-1] - PrefixSum[k][i-1][j-1];
  114.             }
  115.         }
  116.     }
  117.  
  118.     // Gọi hàm giải với khối ban đầu [1, 1, 1] đến [X, Y, Z]
  119.     cout << solve(1, 1, 1, X, Y, Z) << "\n";
  120. }
  121.  
  122. int main() {
  123.     // Tăng tốc độ I/O
  124.     ios_base::sync_with_stdio(false);
  125.     cin.tie(NULL);
  126.  
  127.     int T;
  128.     if (!(cin >> T)) return 0;
  129.  
  130.     while (T--) {
  131.         solve_test_case();
  132.     }
  133.  
  134.     return 0;
  135. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
stdout 
4
https://ideone.com/EyTmXF
language:
C++14 (gcc 8.3)
created:
3 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!