Hướng dẫn giải của [Trại hè HV 2025 Tin 10] GAME
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
Nam phải lần lượt xem (hoặc chơi) các game 1, 2, ..., m. Mỗi game có hai lựa chọn: chơi, tốn a và nhận ki; chỉ xem, tốn b và không nhận gì. Tổng thời gian không vượt quá t, và mục tiêu là tối đa tổng ki của các game đã chơi.
Sub 1: Quy hoạch động theo thời gian đã dùng — ~O(n \cdot t)~, dùng khi ~n, t \le 1000~
Gọi dp[j] là độ hấp dẫn lớn nhất khi đã tốn đúng j đơn vị thời gian sau khi xử lý một số game đầu. Với mỗi game i, từ trạng thái j có thể chuyển sang j + b (chỉ xem) hoặc j + a (chơi, cộng k_i). Sau mỗi game cập nhật đáp án bằng max của dp. Có thể dừng ở bất kỳ game nào nên ta lấy max trên mọi bước. Nếu chỉ nộp sub này: đúng 17/40 test.
Sub 2: Chọn các game chơi bằng hai tập hợp — ~O(n \log n)~
Vì mỗi game đã xem đều tốn đúng b, với m game đầu tổng thời gian tối thiểu là m \cdot b. Phần thời gian còn lại (t - m \cdot b) cho phép chơi thêm (a - b) mỗi game, nên số game được chơi tối đa là P = min(m, (t - m \cdot b) / (a - b)). Khi đó nên chơi P game có k lớn nhất trong m game đầu.
Khi m tăng dần, ta giữ hai multiset: in chứa P giá trị lớn nhất và out chứa phần còn lại, luôn giữ max(out) \le min(in). Thêm k_m vào out, nếu max(out) > min(in) thì đổi chỗ, rồi điều chỉnh kích thước của in bằng P. Cập nhật tổng và lấy max qua mọi m.
Bẫy: đáp án có thể lên tới 2 \cdot 10^5 \cdot 10^9, nên phải dùng long long. Cũng cần dừng khi m \cdot b > t.
Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu. Nếu n, t \le 1000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long t, a, b; // a: xem va choi (cost a, co do hap dan k_i); b: chi xem (cost b, khong co gi)
long long k[200005];
// Mo hinh: Nam phai xem (hoac choi) lan luot game 1, 2, ..., m. Moi game chon "choi" (ton a, nhan k_i)
// hoac "chi xem" (ton b). Tong thoi gian <= t. Muon max tong k_i cua cac game da choi.
// Sub 1: quy hoach dong vet can. dp[j] = do hap dan lon nhat khi da ton dung j don vi thoi gian.
// Sau moi game, cap nhat dp va lay max. O(n * t). Dung khi n, t <= 1000
void sub1() {
vector<long long> dp(t + 1, -1); // -1: trang thai khong dat duoc
dp[0] = 0;
long long ans = 0;
for (int i = 1; i <= n; i++) {
vector<long long> nd(t + 1, -1);
for (long long j = 0; j <= t; j++) {
if (dp[j] < 0) continue;
if (j + b <= t) nd[j + b] = max(nd[j + b], dp[j]); // chi xem game i
if (j + a <= t) nd[j + a] = max(nd[j + a], dp[j] + k[i]); // xem va choi game i
}
dp = nd;
for (long long j = 0; j <= t; j++) ans = max(ans, dp[j]);
}
cout << ans << "\n";
}
// Sub 2: day du (tong quat). O(n log n) cho moi n, t.
// Voi m game dau, can chon P = min(m, (t - m*b)/(a-b)) game co k lon nhat trong m game.
// Giu hai multiset: "in" chua P gia tri lon nhat, "out" chua phan con lai (luon max(out) <= min(in)).
// Khi m tang, them k_m vao "out", sua lai hai tap, roi cap nhat tong. O(n log n)
void sub2() {
multiset<long long> in, out;
long long sumIn = 0, ans = 0;
for (long long m = 1; m <= n; m++) {
if (m * b > t) break;
long long cap = min(m, (t - m * b) / (a - b));
out.insert(k[m]);
// dua gia tri lon nhat sang "in" neu no lon hon min(in)
while (!in.empty() && !out.empty() && *prev(out.end()) > *in.begin()) {
long long x = *prev(out.end()), y = *in.begin();
out.erase(prev(out.end()));
in.erase(in.begin());
in.insert(x); out.insert(y);
sumIn += x - y;
}
// dieu chinh kich thuoc "in" bang cap
while ((long long)in.size() > cap) {
long long y = *in.begin();
in.erase(in.begin()); out.insert(y); sumIn -= y;
}
while ((long long)in.size() < cap && !out.empty()) {
long long x = *prev(out.end());
out.erase(prev(out.end())); in.insert(x); sumIn += x;
}
ans = max(ans, sumIn);
}
cout << ans << "\n";
}
int main() {
freopen("GAME.INP", "r", stdin);
freopen("GAME.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> t >> a >> b;
for (int i = 1; i <= n; i++) cin >> k[i];
if (n <= 1000 && t <= 1000) sub1();
else sub2();
return 0;
}
Bình luận