Hướng dẫn giải của TMP2526_CAU4
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 cửa hàng sao cho tổng thời gian ~\le M~, tổng thức ăn ~\le U~, mỗi cửa hàng tối đa một lần, tổng vui vẻ lớn nhất. Đây là bài cái túi 0/1 với hai ràng buộc.
Sub 1: Thử mọi tập con — ~O(2^R \cdot R)~, dùng khi ~R \le 12~
Duyệt mọi tập con bằng mặt nạ bit, kiểm tra hai ràng buộc, lấy tổng vui vẻ lớn nhất. Dùng đúng miền ~R \le 12~ (với ~R~ lớn hơn không chạy kịp và tràn bit). Trên bộ test thật, sub này xử lý đúng các test thuộc miền của nó: 10/30 test.
Sub 2: Quy hoạch động cái túi hai chiều — ~O(R \cdot M \cdot U)~
Gọi ~dp[t][f]~ là tổng vui vẻ lớn nhất khi dùng tối đa ~t~ phút và ~f~ đơn vị thức ăn. Với mỗi cửa hàng ~i~ cập nhật ~dp[t][f] = \max(dp[t][f], dp[t-T_i][f-F_i] + V_i)~, duyệt ~t~ và ~f~ giảm dần để mỗi cửa hàng chỉ dùng một lần. Tối đa ~150 \cdot 300 \cdot 100 = 4{,}5 \cdot 10^6~ phép tính. Nộp riêng sub này đúng 30/30 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc dữ liệu từ file; nếu ~R \le 12~ 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. Chương trình đạt 30/30 test.
#include <bits/stdc++.h>
using namespace std;
int M, U, R;
int V[155], T[155], F[155];
int dp[305][105];
// Sub 1: thử mọi tập con các cửa hàng, O(2^R * R), dùng khi R <= 12
void sub1() {
int best = 0;
for (int mask = 0; mask < (1 << R); mask++) {
int v = 0, t = 0, f = 0;
for (int i = 0; i < R; i++)
if (mask >> i & 1) { v += V[i]; t += T[i]; f += F[i]; }
if (t <= M && f <= U) best = max(best, v);
}
cout << best << "\n";
}
// Sub 2: cái túi 0/1 hai chiều (thời gian, lượng thức ăn), O(R * M * U)
// dp[t][f] = tổng vui vẻ lớn nhất khi đã dùng tối đa t phút và f đơn vị thức ăn
void sub2() {
for (int i = 0; i < R; i++)
for (int t = M; t >= T[i]; t--)
for (int f = U; f >= F[i]; f--)
dp[t][f] = max(dp[t][f], dp[t - T[i]][f - F[i]] + V[i]);
cout << dp[M][U] << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> M >> U >> R;
for (int i = 0; i < R; i++) cin >> V[i] >> T[i] >> F[i];
if (R <= 12) sub1();
else sub2();
return 0;
}
Bình luận