Hướng dẫn giải của Atcoder Educational DP Contest X - 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.
Lưu ý: Cách tối ưu nhất để sắp xếp các khối theo chiều từ trên đỉnh xuống dưới đáy là sắp xếp chúng theo chiều tăng dần cân nặng ~w~ và sức chịu nặng ~s~.
Xét ~2~ cách xếp ~2~ khối ~a~ và ~b~:
- Nếu như khối ~a~ ở vị trí đáy, ta có sức chịu nặng của toà tháp là: ~s_a - w_b~
- Nếu như khối ~b~ ở vị trí đáy, ta có sức chịu nặng của toà tháp là: ~s_b - w_a~
Hiển nhiên, ta sẽ chọn cách xếp để sức chịu nặng của tọa tháp lớn nhất có thể, là ~max(s_a - w_b, s_b - w_a)~. Dễ nhận thấy thay vì so sánh các giá trị ~(s_a - w_b)~, ~(s_b - w_a)~, ta có thể sắp xếp thứ tự của các khối bằng cách so sánh các giá trị ~(s_a + w_a)~, ~(s_b + w_b)~.
Để tối ưu hoá sức chịu nặng của toà tháp, chúng ta đặt khối có tổng ~s_i + w_i~ thấp hơn lên đỉnh. Đến đây, ta nhận thấy bài toán đã đưa về dạng bài toán quy hoạch động khá quen thuộc - Bài toán cái túi .
Nhận xét rằng giá trị của tháp phụ thuộc vào ~2~ yếu tố: có bao nhiêu khối đã được xét và trọng lượng của các khối. Do đó hướng giải sẽ là dùng mảng ~2~ chiều ~f[i][j]~: tổng giá trị lớn nhất của tháp khi xét ~i~ khối đầu và trọng lượng của tháp chưa vượt quá ~j~.
Tính ~f[i][j]~: khối đang xét là khối thứ ~i~ với trọng lượng của tháp bằng ~j~. Khi đó có ~2~ khả năng xảy ra:
- Nếu chọn khối ~i~ làm đáy tháp, tổng cân nặng các khối trên tháp trước đó không được quá ~j − w_i~. Tất nhiên ~j \le w_i + s_i~.
- Nếu không chọn khối ~i~, tổng cân nặng của tháp là như cũ (như lúc trước khi chọn khối ~i~): ~f[i − 1][j]~.
Tóm lại ta có:
Gọi ~dp[j]~ là giá trị tối đa mà tháp có thể đạt được với tổng cân nặng của tháp không vượt quá ~j~. Xét dãy theo chiều tăng dần đã sắp xếp ở trên, xét khối thứ ~i~, với ~w_i \le j \le w_i + s_i~, ta rút ra công thức sau:
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e3 + 1; const int MAX_W = 2e4 + 1; long long dp[MAX_W]; int w[MAX_N], s[MAX_N], v[MAX_N], p[MAX_N]; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; for(int i = 0; i < N; ++i) cin >> w[i] >> s[i] >> v[i]; for(int i = 0; i < N; ++i) p[i] = i; sort(p, p + N, [&](const int &a, const int &b) { return w[a] + s[a] < w[b] + s[b]; }); for(int x = 0; x < N; ++x) { int i = p[x]; for(int j = s[i] + w[i]; j >= w[i]; --j) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << *max_element(dp, dp + MAX_W) << endl; }
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
tại kiểu bạn tính theo cái j - w[i] nên nếu duyệt xuyên bạn sẽ thay đổi giá trị j - w[i] trước nên sẽ sai kq