Hướng dẫn giải của [VTT Q4 Contest 04] Bài 3: Xây tháp [TOWER]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Chọn tập khối xếp chồng được thành tháp (khối trên nằm trọn trong khối dưới, được xoay) sao cho tổng giá trị lớn nhất. Xoay được nên ta chuẩn hóa mỗi khối thành ~a \ge b~; khi đó khối ~x~ đặt lên khối ~y~ được khi ~a_x \le a_y~ và ~b_x \le b_y~.
Sub 1: Vét cạn — ~O(2^n \cdot n \log n)~, dùng khi ~n \le 20~
Duyệt mọi tập con khối, sắp xếp theo ~a~ giảm dần (hòa thì theo ~b~ giảm dần) rồi kiểm tra cạnh ~b~ có không tăng không; nếu có thì tập đó xếp được thành tháp, cập nhật đáp án bằng tổng giá trị. Nếu chỉ nộp sub này: đúng 3/10 test, các test ~n~ lớn bị quá giờ hoặc không chạy hết.
Sub 2: Quy hoạch động — ~O(n^2)~
Sau khi chuẩn hóa và sắp xếp các khối theo ~a~ giảm dần (hòa theo ~b~ giảm dần), một tháp chính là một dãy con có ~b~ không tăng. Gọi ~f_i~ là tổng lớn nhất của tháp có khối thứ ~i~ ở trên cùng: ~f_i = g_i + \max f_j~ với ~j < i~ và ~b_j \ge b_i~ (hoặc chỉ ~g_i~). Đáp án là ~\max f_i~. Bẫy: phải chuẩn hóa ~a \ge b~ trước khi sắp xếp, và so sánh không nghiêm ngặt vì được phép bằng nhau. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu và chuẩn hóa từng khối; ~n \le 20~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[105], b[105];
long long g[105];
// Sub 1: duyệt mọi tập con khối (2^n), kiểm tra xếp được thành tháp không — dùng khi n ≤ 20
void sub1() {
long long best = 0;
for (int mask = 1; mask < (1 << n); mask++) {
vector<int> id;
long long tong = 0;
for (int i = 0; i < n; i++)
if (mask >> i & 1) { id.push_back(i); tong += g[i]; }
if (tong <= best) continue;
// sắp xếp giảm dần theo (a, b); xếp được khi cạnh b cũng không tăng
sort(id.begin(), id.end(), [&](int x, int y) {
if (a[x] != a[y]) return a[x] > a[y];
return b[x] > b[y];
});
bool ok = true;
for (size_t k = 1; k < id.size(); k++)
if (b[id[k]] > b[id[k - 1]]) { ok = false; break; }
if (ok) best = tong;
}
cout << best << "\n";
}
// Sub 2: QHĐ dãy con giảm có trọng số lớn nhất — ~O(n^2)~
void sub2() {
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) {
if (a[x] != a[y]) return a[x] > a[y];
return b[x] > b[y];
});
vector<long long> f(n); // f[i]: tổng lớn nhất của tháp có khối id[i] ở trên cùng
long long best = 0;
for (int i = 0; i < n; i++) {
f[i] = g[id[i]];
for (int j = 0; j < i; j++)
if (b[id[j]] >= b[id[i]]) f[i] = max(f[i], f[j] + g[id[i]]);
best = max(best, f[i]);
}
cout << best << "\n";
}
int main() {
freopen("TOWER.INP", "r", stdin);
freopen("TOWER.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> g[i];
if (a[i] < b[i]) swap(a[i], b[i]); // chuẩn hóa a ≥ b (xoay được)
}
if (n <= 20) sub1();
else sub2();
}
Bình luận