Bỏ qua

DP trên DAG

Định nghĩa

DAG chính là Đồ thị có hướng không chu trình. Một số quan hệ nhị phân trong các bài toán thực tế có thể được mô hình hóa bằng DAG, từ đó chuyển đổi các bài toán này thành bài toán tìm đường đi dài (ngắn) nhất trên DAG.

Giải thích

Lấy bài toán này làm ví dụ để phân tích quá trình mô hình hóa DAG.

Ví dụ UVa 437 Tòa tháp Babylon The Tower of Babylon

Có \(n (n\leqslant 30)\) loại khối gạch, biết độ dài ba cạnh, mỗi loại có số lượng vô hạn. Yêu cầu chọn một số khối lập phương chồng thành một cột cao nhất có thể (mỗi khối gạch có thể tự chọn một cạnh làm chiều cao), sao cho chiều dài và chiều rộng mặt đáy của mỗi khối gạch phải nhỏ hơn nghiêm ngặt chiều dài và chiều rộng mặt đáy của khối gạch nằm dưới nó. Tìm chiều cao tối đa của tháp.

Quá trình

Xây dựng DAG

Vì chiều dài và chiều rộng mặt đáy của mỗi khối gạch phải nhỏ hơn nghiêm ngặt khối gạch bên dưới, nên không khó để dùng quan hệ này làm cơ sở dựng đồ thị, và bài toán này sẽ chuyển thành bài toán đường đi dài nhất.

Nói cách khác, nếu khối gạch \(j\) có thể đặt lên trên khối gạch \(i\), thì giữa \(i\) và \(j\) tồn tại một cạnh \((i, j)\), và trọng số cạnh chính là chiều cao được chọn của khối gạch \(j\).

Một vấn đề khác của bài này là mỗi khối gạch có ba cách chọn chiều cao, vậy dựng đồ thị thế nào cho phù hợp?

Ta có thể phân rã mỗi khối gạch thành ba cách xếp chồng, tức là chia một khối gạch thành ba thực thể khác nhau, mỗi thực thể chọn một cạnh khác nhau làm chiều cao.

Điểm bắt đầu ban đầu là mặt đất, mặt đất có diện tích đáy vô hạn, nên mặt đất có thể nối đến bất kỳ khối gạch nào. Tất nhiên khi lập trình chúng ta không cần viết cụ thể giá trị vô hạn.

Giả sử có hai khối gạch với các cạnh lần lượt là \(31, 41, 59\) và \(33, 83, 27\), thì toàn bộ DAG sẽ như hình dưới đây.

Trong hình, khung nét liền màu xanh lam biểu thị một nhóm khối gạch được phân rã từ một khối gạch gốc. Sở dĩ dùng \(\{\}\) để biểu thị cạnh đáy là vì một khi khối gạch đã chọn chiều cao, thứ tự chiều dài và chiều rộng mặt đáy là không quan trọng (miễn là thỏa mãn điều kiện nhỏ hơn).

Khung nét đứt màu vàng biểu thị phần tính toán bị lặp lại, có thể sử dụng phương pháp Tìm kiếm ghi nhớ để tránh việc này.

Chuyển trạng thái

Yêu cầu của đề bài là chiều cao tối đa của tháp, đã được chuyển thành bài toán đường đi dài nhất. Điểm bắt đầu như đã nêu trên là mặt đất, vậy điểm kết thúc ở đâu? Hiển nhiên điểm kết thúc được xác định tự nhiên khi không thể đặt thêm khối gạch nào lên trên một khối gạch nữa.

Tiếp theo chúng ta xem xét phương trình chuyển trạng thái.

Gọi \(d(i, r)\) là chiều cao tối đa khi khối gạch thứ \(i\) nằm ở dưới cùng và được đặt theo cách thứ \(r\). Khi đó ta có phương trình chuyển trạng thái sau:

\[ d(i, r) = \max\left\{d(j, r') + h\right\} \]

Trong đó \(j\) là tất cả những khối gạch có thể đặt lên trên khối gạch \(i\) khi \(i\) đang ở trạng thái \(r\), \(r'\) tương ứng với cách đặt của \(j\) lúc đó, và \(h\) là chiều cao của khối gạch \(i\) khi chọn cách đặt thứ \(r\).

Cài đặt 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 30 + 5;
constexpr int MAXV = 500 + 5;
int d[MAXN][3];
int x[MAXN], y[MAXN], z[MAXN];

int babylon_sub(int c, int rot, int n) {
  if (d[c][rot] != -1) {
    return d[c][rot];
  }
  d[c][rot] = 0;
  int base1, base2;
  if (rot == 0) {  // 处理三个方向
    base1 = x[c];
    base2 = y[c];
  }
  if (rot == 1) {
    base1 = y[c];
    base2 = z[c];
  }
  if (rot == 2) {
    base1 = x[c];
    base2 = z[c];
  }
  for (int i = 0; i < n; i++) {  // 根据不同条件，分别调用不同的递归
    if ((x[i] < base1 && y[i] < base2) || (y[i] < base1 && x[i] < base2))
      d[c][rot] = max(d[c][rot], babylon_sub(i, 0, n) + z[i]);
    if ((y[i] < base1 && z[i] < base2) || (z[i] < base1 && y[i] < base2))
      d[c][rot] = max(d[c][rot], babylon_sub(i, 1, n) + x[i]);
    if ((x[i] < base1 && z[i] < base2) || (z[i] < base1 && x[i] < base2))
      d[c][rot] = max(d[c][rot], babylon_sub(i, 2, n) + y[i]);
  }
  return d[c][rot];
}

int babylon(int n) {
  for (int i = 0; i < n; i++) {
    d[i][0] = -1;
    d[i][1] = -1;
    d[i][2] = -1;
  }
  int r = 0;
  for (int i = 0; i < n; i++) {  // 三种建法
    r = max(r, babylon_sub(i, 0, n) + z[i]);
    r = max(r, babylon_sub(i, 1, n) + x[i]);
    r = max(r, babylon_sub(i, 2, n) + y[i]);
  }
  return r;
}

int main() {
  int t = 0;
  while (true) {  // 死循环求答案
    int n;
    cin >> n;
    if (n == 0) break;  // 没有砖头了就停止
    t++;
    for (int i = 0; i < n; i++) {
      cin >> x[i] >> y[i] >> z[i];
    }
    cout << "Case " << t << ":"
         << " maximum height = " << babylon(n);  // 递归
    cout << endl;
  }
  return 0;
}
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply