Hướng dẫn giải của Ăn vặt (đề HSG 12 Phú Thọ 2025-2026)
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 (mỗi cửa hàng tối đa một lần) sao cho tổng thời gian ~\le M~, tổng thức ăn ~\le U~ và 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: Vét cạn — ~O(2^R \cdot R)~, dùng khi ~R \le 20~
Duyệt mọi tập con cửa hàng, kiểm tra hai ràng buộc và lấy tổng vui vẻ lớn nhất. Nếu chỉ nộp sub này: đúng 10/30 test.
Sub 2: Quy hoạch động hai chiều — ~O(R \cdot M \cdot U)~
~dp[t][f]~ là tổng vui vẻ lớn nhất khi tổng thời gian không quá ~t~ và thức ăn không quá ~f~. Với mỗi cửa hàng, cập nhật ~dp[t][f] = \max(dp[t][f], dp[t - T_i][f - F_i] + V_i)~ với ~t~ và ~f~ chạy giảm dần để mỗi cửa hàng chỉ dùng một lần. Chi phí tối đa ~150 \cdot 300 \cdot 100~ phép tính. Nếu chỉ nộp sub này: đúng 30/30 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~R \le 20~ thì 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 M, U, R;
int V[155], T[155], F[155];
// Sub 1: vét cạn mọi tập cửa hàng, O(2^R * R), dùng khi R <= 20
void sub1() {
int best = 0;
for (int mask = 0; mask < (1 << R); mask++) {
int t = 0, f = 0, v = 0;
for (int i = 0; i < R; i++)
if (mask >> i & 1) { t += T[i]; f += F[i]; v += V[i]; }
if (t <= M && f <= U) best = max(best, v);
}
printf("%d\n", best);
}
// Sub 2: quy hoạch động kiểu cái túi hai chiều, O(R * M * U)
// dp[t][f] = tổng vui vẻ lớn nhất khi tổng thời gian không quá t và lượng thức ăn không quá f
static int dp[305][105];
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]);
printf("%d\n", dp[M][U]);
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
scanf("%d %d %d", &M, &U, &R);
for (int i = 0; i < R; i++) scanf("%d %d %d", &V[i], &T[i], &F[i]);
if (R <= 20) sub1();
else sub2();
return 0;
}
Bình luận