Xây tháp
Đề bài
Có $n$ khối đá cẩm thạch được đánh số từ 1 tới $n$. Khối đá thứ $i$ có dạng hình hộp chữ nhật với mặt đáy và mặt trên là hình chữ nhật kích thước $a_i \times b_i$. Khối đá thứ $i$ có giá trị là $g_i$ đồng.
Người ta cần xây một tháp bằng cách đặt các khối đá này chồng lên nhau theo quy tắc:
- Mặt đáy của khối đá ở bên trên được đặt trọn vẹn trên mặt trên của khối đá ở bên dưới.
- Các cạnh đáy của các khối đá song song với nhau.
Yêu cầu: hãy tìm một phương án xây tháp với tổng giá trị của các khối đá xây tháp là lớn nhất.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 100)$.
- Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa 3 số nguyên dương $a_i, b_i$ và $g_i$ là kích thước mặt đáy và giá trị của khối đá thứ $i$ $(a_i, b_i, g_i \le 10\,000)$.
Kết quả: tổng giá trị các khối đá của tháp mà bạn xây được.
Lưu ý của thầy trên CLUE: đề bài tuy không nói rõ nhưng hãy hiểu rằng 1 khối đá chỉ chịu trực tiếp 1 khối đá khác bên trên, tức là A chứa B ở trên rồi B có thể chứa C ở trên rồi C chứa D ở trên… thì được, chứ không có chuyện A chứa cùng lúc cả B và C (dù cho A đủ chỗ trống để chứa cả B và C).
3
3 4 3
5 2 4
2 3 59Giải thích ví dụ: chồng khối đá thứ 3 lên khối đá thứ 2 được tháp có tổng giá trị lớn nhất bằng $4 + 5 = 9$. Khối 3 có đáy $2 \times 3$, khối 2 có đáy $5 \times 2$: phải xoay khối 3 thành $3 \times 2$ thì mới đặt trọn trên $5 \times 2$ được ($3 \le 5$, $2 \le 2$).
Lời mở đầu
Nhờ lưu ý "mỗi khối chỉ đỡ trực tiếp 1 khối", tháp chính là một dãy khối đá, khối sau nhỏ hơn (hoặc bằng) khối trước theo cả 2 chiều. Bài toán trở thành: tìm dãy "giảm dần theo 2 chiều" có tổng giá trị lớn nhất – một biến thể có trọng số của bài dãy con tăng dài nhất. Mình sẽ đi từ quay lui, sang đệ quy có nhớ, rồi tới quy hoạch động bảng, mỗi cách đều nộp thử trên bộ test thật.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | Số khối $n$ | $a, b, g$ lớn nhất | Đáp án |
|---|---|---|---|
| 001–010 | 3–9 | 10 | 11 → 48 |
| 011–020 | 3–10 | 9.846 | 15 → 19.057 |
| 021–100 | 100 | 9.998 | 33.044 → 98.524 |
Đề không chia subtask, nhưng bộ test có 2 mức rõ ràng: 20 test đầu $n \le 10$, 80 test sau $n = 100$. Đáp án tối đa chỉ $100 \cdot 10^4 = 10^6$ nên dùng int thoải mái. Mình còn kiểm tra thêm 2 điều mà đề không nói rõ:
- Được xoay khối đá 90° (đổi vai trò $a_i$ và $b_i$). Ngay ví dụ: khối 3 ($2 \times 3$) đặt lên khối 2 ($5 \times 2$) chỉ được khi xoay thành $3 \times 2$. Mình thử bản không cho xoay thì chỉ đúng 6/100 test.
- Hai khối cùng kích thước vẫn chồng lên nhau được ("đặt trọn vẹn" cho phép bằng). Có 92 test chứa 2 khối cùng kích thước; bản dùng dấu $<$ thay cho $\le$ chỉ đúng 4/100 test.
| Mức | Điều kiện | Test | Cách 1 quay lui | Cách 2 đệ quy có nhớ | Cách 3 QHĐ bảng |
|---|---|---|---|---|---|
| 1 | $n \le 10$ | 001–020 | qua | qua | qua |
| 2 | $n = 100$ | 021–100 | quá thời gian | qua | qua |
Ý tưởngXoay về cạnh ngắn trước, sắp xếp, rồi làm như LIS
Bước 1 – chuẩn hoá: với mỗi khối, đặt $x = \min(a, b)$, $y = \max(a, b)$. Khi đó khối $j$ đặt được lên khối $i$ (có xoay hay không) khi và chỉ khi $x_j \le x_i$ và $y_j \le y_i$. (Nếu cạnh ngắn của $j$ đã không lọt cạnh ngắn của $i$ thì xoay kiểu gì cũng không lọt.)
Bước 2 – sắp xếp các khối tăng dần theo $(x, y)$. Khối đặt được lên khối $i$ thì có $x$ và $y$ đều không lớn hơn, nên luôn đứng trước $i$ trong thứ tự này (hai khối bằng nhau thì khối nào đứng trước cũng được).
$f[i] = g_i + \max\big(0,\ \max\{ f[j] : j < i,\ x_j \le x_i,\ y_j \le y_i \}\big)$. Đáp án là $\max f[i]$.
Em nhập các khối (mỗi khối 3 số $a\ b\ g$) rồi bấm Tiếp. Bên trái là bảng $f$ sau khi sắp xếp, bên phải vẽ tháp tốt nhất đang có với khối $i$ ở đáy (nhìn từ bên cạnh, bề rộng là cạnh dài $y$):
Cách 1Quay lui thử mọi cách chồng
Cứ xây tháp từ dưới lên: hàm Try(top, sum) nghĩa là "khối trên cùng đang là top, tháp có tổng giá trị sum". Mỗi lần được gọi thì cập nhật kỷ lục, rồi thử đặt lên trên mọi khối chưa dùng mà vừa với top. Khối số 0 là "mặt đất" – rộng vô hạn, khối nào đặt lên cũng được.
- Phải có mảng
used[]: hai khối cùng kích thước đặt được lên nhau theo cả 2 chiều, nếu không đánh dấu thì đệ quy chạy vòng tròn mãi. used[i] = falsesau lời gọi là bước quay lui: nhấc khối $i$ xuống để thử khối khác.
Kết quả chạy thật: đúng 20/100 test – quá thời gian test 021–100. Với $n = 100$, số cách chồng tháp tăng theo cấp số nhân nên chạy không nổi.
Cách 2Đệ quy có nhớ
Quay lui chậm vì câu hỏi "tháp tốt nhất có khối $i$ ở đáy là bao nhiêu?" bị tính lại rất nhiều lần. Đáp án câu hỏi này không phụ thuộc phía dưới $i$ là gì, nên ta tính một lần rồi nhớ lại trong memo[i]. Để đệ quy không chạy vòng tròn giữa các khối bằng nhau, ta sắp xếp trước và chỉ cho khối $j < i$ đặt lên khối $i$.
memo[i] = -1nghĩa là chưa tính (đáp án luôn dương).- Độ sâu đệ quy tối đa $n = 100$ tầng, an toàn.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,003 giây.
Cách 3Quy hoạch động bảng
Bỏ đệ quy, tính thẳng $f[1], f[2], \ldots, f[n]$ theo thứ tự đã sắp xếp – khi tính $f[i]$ thì mọi $f[j]$ với $j < i$ đã có sẵn.
sorttrênarray<int, 3>so sánh theo thứ tự $(x, y, g)$ – đúng cái ta cần.- Không cần
max(0, ...)riêng vìf[i]được khởi tạo bằngg[i](tháp chỉ có 1 khối).
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,004 giây.
Bản Python (mình viết thêm, chấm trên cùng bộ test): cách 1 được 20/100 test – quá thời gian test 021–100; cách 2 được 100/100 test, chậm nhất 0,028 giây; cách 3 được 100/100 test, chậm nhất 0,025 giây.
Nhận xét
Đăng nhận xét