Hướng dẫn giải của Đề án cây xanh
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ời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
,
Editorial for seq: Đề án cây xanh
Hiểu bài toán
Bài toán yêu cầu tìm cách chọn các cây để chặt sao cho tổng giá trị của các cây bị chặt là lớn nhất, với ràng buộc: không được chặt quá k-1 cây liên tiếp. Tức là trong mọi đoạn liên tiếp dài k cây, phải có ít nhất 1 cây được giữ lại (không bị chặt). Ta cần tính tổng giá trị lớn nhất của các cây có thể chặt.
Các cách tiếp cận
Cách Quy hoạch động cơ bản - Duyệt đoạn chặt
#include <stdio.h>
#include <string.h>
int main() {
int n, k;
scanf("%d %d", &n, &k);
int v[n + 1];
int sum[n + 1];
v[0] = 0;
sum[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
sum[i] = v[i] + sum[i - 1];
}
int dp[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1]; // Không chặt cây thứ i
// Cố gắng chặt j cây liên tiếp ngay trước cây i (vị trí i-j+1 ... i)
// j chạy từ 1 đến k-1 (vì không được phép chặt quá k-1 liên tiếp)
for (int j = 1; j < k && j <= i; j++) {
int value = sum[i] - sum[i - j]; // Tổng giá trị của j cây vừa chặt
if (i - j - 1 >= 0) value += dp[i - j - 1]; // Cộng dồn giá trị tối ưu trước đó
if (dp[i] < value) dp[i] = value;
}
}
printf("%d", dp[n]);
return 0;
}
- Time Complexity: O(n * k)
- Space Complexity: O(n)
Định nghĩa dp[i] là tổng giá trị lớn nhất có thể thu được từ i cây đầu tiên. Với mỗi vị trí i, ta có hai lựa chọn: hoặc không chặt cây i (dp[i] = dp[i-1]), hoặc chặt một đoạn ngay trước i. Ta duyệt j từ 1 đến k-1, giả sử chặt j cây cuối cùng (từ i-j+1 đến i). Khi đó, tổng giá trị là dp[i-j-1] (tối ưu trước đoạn chặt) cộng với tổng giá trị của j cây vừa chặt. Ta cập nhật dp[i] bằng giá trị lớn nhất trong các trường hợp. Lưu ý khoảng lặng 1 cây giữa các đoạn chặt (i-j-1).
Cách Quy hoạch động tối ưu - Sliding Window Maximum (Deque)
#include <iostream>
#include <vector>
#include <deque>
#include <numeric>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> v(n + 1);
vector<long long> pref(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> v[i];
pref[i] = pref[i - 1] + v[i];
}
// dp[i] là giá trị lớn nhất đến cây thứ i
vector<long long> dp(n + 1, 0);
// dq lưu chỉ số j, giá trị xét là dp[j] - pref[j]
deque<int> dq;
dq.push_back(0);
for (int i = 1; i <= n; i++) {
// Loại bỏ các chỉ số quá cũ (độ dài đoạn chặt > k-1)
// Nếu chặt đoạn từ j+1 đến i, độ dài là i - j.
// Ràng buộc: i - j <= k - 1 => j >= i - (k - 1)
while (!dq.empty() && dq.front() < i - (k - 1)) {
dq.pop_front();
}
// dp[i] = pref[i] + max(dp[j] - pref[j]) với j trong khoảng [i-k, i-1]
// Lưu ý: j = i-1 tương ứng với việc không chặt đoạn mới, chỉ là dp[i-1] + v[i]?
// Công thức đúng: dp[i] = max(dp[i-1], pref[i] + max(dp[j] - pref[j]))
// Nếu j = i-1, dp[i-1] - pref[i-1] + pref[i] = dp[i-1] + v[i].
// Nếu j < i-1, ta đang chặt đoạn j+1...i.
// Công thức gom gọn: dp[i] = pref[i] + max(0, max_{j}(dp[j] - pref[j]))
// Đoạn j+1...i được chặt hoàn toàn.
long long best = -2e18;
if (!dq.empty()) best = dp[dq.front()] - pref[dq.front()];
// Nếu không chặt gì thêm, dp[i] = dp[i-1]
// Công thức: dp[i] = max(dp[i-1], pref[i] + best)
// Nếu best là dp[j]-pref[j], thì pref[i] + best = dp[j] + (pref[i]-pref[j])
// Tức là dp[j] + sum(j+1...i).
dp[i] = max(dp[i-1], pref[i] + best);
// Thêm i vào deque cho các bước sau
// Giá trị cần so sánh là dp[i] - pref[i]
long long val = dp[i] - pref[i];
while (!dq.empty() && (dp[dq.back()] - pref[dq.back()]) <= val) {
dq.pop_back();
}
dq.push_back(i);
}
cout << dp[n] << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Công thức dp[i] = max(dp[i-1], max{1<=j<=k-1} (dp[i-j-1] + sum(i-j+1...i))). Biến đổi: dp[i] = max(dp[i-1], max{j} (dp[i-j-1] + (pref[i] - pref[i-j]))) Đặt idx = i-j-1, ta tìm max(dp[idx] - pref[idx]) + pref[i] với idx chạy từ i-k đến i-2. Sử dụng Deque để tìm max trong cửa sổ trượt O(1).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n * k) | O(n) | Quy hoạch động cơ bản - Duyệt đoạn chặt |
| 2 | O(n) | O(n) | Quy hoạch động tối ưu - Sliding Window Maximum (Deque) |
Bài học kinh nghiệm
- Bài toán có tính chất tối ưu con và có thể chia nhỏ thành các bài toán nhỏ hơn (quy hoạch động).
- Ràng buộc 'không chặt quá k-1 liên tiếp' có thể hiểu là giữa hai đoạn cây bị chặt phải có ít nhất một cây không bị chặt.
- Biến đổi công thức quy hoạch động thành dạng tìm max trên một cửa sổ trượt giúp giảm độ phức tạp từ O(n*k) xuống O(n).
Lỗi thường gặp
- Quên không xử lý trường hợp đoạn chặt nằm ở vị trí đầu hoặc cuối dãy.
- Lầm tưởng bài toán là tìm dãy con liên tiếp có tổng lớn nhất (Maximum Subarray Sum), trong khi đây là bài toán chọn các đoạn để tối ưu hóa tổng thể.
- Sai lệch khi tính chỉ số trong công thức quy hoạch động, đặc biệt là khoảng lặng giữa các đoạn chặt.
Bình luận