Hướng dẫn giải của [KSCUM VT 02] CÂU 4: Công việc
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Mỗi công nhân i hoặc làm riêng (mất ti), hoặc phối hợp với người i+1 (mất pi cho cả hai). Mỗi người chỉ thuộc tối đa một cặp, nên các cặp không được chồng lên nhau. Cần chọn các cặp và các người làm riêng sao cho tổng thời gian nhỏ nhất.
Sub 1: Đệ quy vét cạn — ~O(\phi^N)~, dùng khi ~N \le 25~
Hàm rec(i): hoặc làm riêng công nhân i rồi xét rec(i+1), hoặc ghép i với i+1 rồi xét rec(i+2). Lấy giá trị nhỏ hơn. Không nhớ lại kết quả nên số lần gọi tăng rất nhanh. Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: Quy hoạch động — ~O(N)~
Gọi dp[i] là thời gian nhỏ nhất để hoàn thành i công việc đầu. Có dp[i] = min(dp[i-1] + ti, dp[i-2] + p{i-1}). Đáp án là dp[N].
Bẫy: tổng có thể lên tới khoảng 10^{12}, dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu. Nếu N \le 25 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> t; // t[1..N]: thoi gian lam mot minh
vector<long long> p; // p[1..N-1]: thoi gian khi cong nhan i va i+1 phoi hop
// Sub 1: de quy vet can. Cong nhan i hoac lam rieng (t_i, roi xet i+1), hoac phoi hop voi i+1
// (p_i, roi xet i+2). Khong nho lai nen thoi gian tang theo cap so Fibonacci. Dung khi N <= 25
long long rec1(int i) {
if (i > N) return 0;
long long best = t[i] + rec1(i + 1);
if (i < N) best = min(best, p[i] + rec1(i + 2));
return best;
}
void sub1() {
cout << rec1(1) << "\n";
}
// Sub 2: quy hoach dong. dp[i] = thoi gian nho nhat de hoan thanh i cong viec dau tien.
// dp[i] = min(dp[i-1] + t_i, dp[i-2] + p_{i-1}). O(N)
void sub2() {
vector<long long> dp(N + 1, 0);
dp[0] = 0;
for (int i = 1; i <= N; i++) {
dp[i] = dp[i - 1] + t[i];
if (i >= 2) dp[i] = min(dp[i], dp[i - 2] + p[i - 1]);
}
cout << dp[N] << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
t.assign(N + 2, 0);
p.assign(N + 2, 0);
for (int i = 1; i <= N; i++) cin >> t[i];
for (int i = 1; i <= N - 1; i++) cin >> p[i];
if (N <= 25) sub1();
else sub2();
return 0;
}
Bình luận