Quy hoạch động (2)
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 90 phút
- Học trước
- Quy hoạch động (1)
- Chủ đề
- quy hoạch động
- Trạng thái
Kiến thức cơ bản
Nhắc lại: khuôn quy hoạch động
Tuần trước, em đã làm quen với quy hoạch động (DP) qua bài leo cầu thang: thay vì tính đi tính lại cùng một việc, ta lưu kết quả của các bài toán nhỏ vào mảng dp rồi dùng chúng để tính bài toán lớn hơn. Bài DP nào cũng đi qua 4 bước:
| Bước | Câu hỏi cần trả lời |
|---|---|
| 1. Trạng thái | dp[i] có nghĩa là gì? |
| 2. Công thức | dp[i] được tính từ những ô nào đã biết? |
| 3. Khởi tạo | Những ô đầu tiên có giá trị bao nhiêu? |
| 4. Đáp án | Lấy đáp án ở đâu trong mảng dp? |
Ở bài leo cầu thang, dp[i] chỉ nhìn lại hai ô ngay trước nó và đáp án là ô cuối cùng. Tuần này có hai điều mới: dp[i] được nhìn lại mọi ô phía trước, và đáp án có thể là giá trị lớn nhất trong cả mảng dp.
Dãy con và đoạn con
Cho dãy a = 5 1 8 2 9. Đoạn con là các phần tử đứng liền nhau, ví dụ 1 8 2. Dãy con là chọn một số phần tử, giữ nguyên thứ tự nhưng được bỏ qua, ví dụ 5 8 9 (bỏ qua 1 và 2). Mọi đoạn con đều là dãy con, nhưng dãy con chưa chắc là đoạn con.
Tuần này ta giải hai bài kinh điển: một bài về dãy con (dãy con tăng dài nhất) và một bài về đoạn con (đoạn có tổng lớn nhất). Cả hai dùng chung một mẹo: “kết thúc tại i”.
Mẹo chính: dp[i] kết thúc tại vị trí i
Gấu Po leo đồi qua một hàng bậc đá. Po tự hỏi: “Nếu mình bắt buộc phải đứng ở bậc i, thì đến đây mình đã leo được nhiều nhất bao nhiêu bậc?”. Bắt buộc đứng ở bậc i làm bài toán nhỏ trở nên rõ ràng: ta chỉ cần xét xem bậc i nối được vào sau những bậc nào. Còn đáp án cuối cùng chỉ là chọn bậc i tốt nhất.
Dãy con tăng dài nhất
Bài toán: cho dãy a gồm n số. Hãy chọn một dãy con tăng hẳn (số sau lớn hơn số trước) sao cho dãy con đó dài nhất. Ví dụ với a = 10 22 9 33 21 50 41 60, dãy con tăng dài nhất là 10 22 33 50 60, dài 5.
Bốn bước
- Trạng thái: dp[i] là độ dài dãy con tăng dài nhất mà phần tử cuối cùng chính là a[i].
- Công thức: xét mọi vị trí j đứng trước i. Nếu a[j] < a[i] thì nối a[i] vào sau dãy đang kết thúc tại j, được dp[j] + 1. Lấy giá trị lớn nhất: dp[i] = max(dp[i], dp[j] + 1).
- Khởi tạo: dp[i] = 1 với mọi i (dãy chỉ gồm một mình a[i]).
- Đáp án: giá trị lớn nhất trong mảng dp. Đáp án không phải dp[n - 1], vì dãy tốt nhất chưa chắc kết thúc ở phần tử cuối.
i : 0 1 2 3 4 5 6 7
a[i] : 10 22 9 33 21 50 41 60
dp[i] : 1 2 1 3 2 4 4 5
^ đáp án = max(dp) = 5
Xét i = 5 (a[5] = 50): các phần tử đứng trước và nhỏ hơn 50 là 10, 22, 9, 33, 21 với dp lần lượt là 1, 2, 1, 3, 2. Lớn nhất là 3 (tại số 33), nên dp[5] = 3 + 1 = 4.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> dp(n, 1); // mỗi phần tử tự là dãy dài 1
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) { // a[i] nối được vào sau a[j]
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]); // đáp án là dp lớn nhất
}
cout << ans;
return 0;
}
Độ phức tạp: hai vòng for lồng nhau, khoảng n2/2 phép so sánh. Với n = 1000 máy chỉ mất một cái chớp mắt (khoảng 5 × 105 phép), với n = 5000 vẫn chạy nhanh (khoảng 1,25 × 107 phép). Nhưng với n = 105 cần 5 × 109 phép, quá chậm: bài toán n lớn cần một cách khác (xem bài thử thách ở phần tự luyện).
Các biến thể chỉ cần đổi một dấu
- Tăng không ngặt (cho phép bằng nhau): đổi a[j] < a[i] thành a[j] <= a[i].
- Giảm dần hẳn: đổi thành a[j] > a[i].
- Xâu ký tự: làm y hệt, vì hai chữ cái cũng so sánh được bằng < và <=.
- Xóa ít nhất bao nhiêu phần tử để dãy còn lại tăng dần: đáp án là n trừ đi độ dài dãy con tăng dài nhất.
Truy vết: in ra cả dãy (không bắt buộc)
Muốn in cả dãy chứ không chỉ độ dài, ta thêm mảng truoc[i]: vị trí j đã giúp dp[i] đạt giá trị lớn nhất (ghi -1 nếu a[i] đứng đầu dãy). Cuối cùng đi ngược từ vị trí kết thúc tốt nhất, giống như lần theo dấu chân của Po.
vector<int> dp(n, 1), truoc(n, -1);
int best = 0; // vị trí kết thúc của dãy dài nhất
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
truoc[i] = j; // ghi nhớ: đứng trước i là j
}
}
if (dp[i] > dp[best]) best = i;
}
vector<int> path;
for (int i = best; i != -1; i = truoc[i]) path.push_back(a[i]);
reverse(path.begin(), path.end()); // đi ngược nên phải đảo lại
Đoạn con có tổng lớn nhất
Thỏ bán mật ong n ngày liên tiếp. Ngày thứ i Thỏ lãi a[i] đồng (số âm là lỗ). Thỏ muốn chọn một đoạn ngày liên tiếp có tổng lãi lớn nhất. Cách vét cạn thử mọi cặp (l, r) cần khoảng n2 phép: với n = 105 là 1010, quá chậm. Quy hoạch động giải bài này chỉ trong n phép.
Bốn bước
- Trạng thái: dp[i] là tổng lớn nhất của một đoạn kết thúc đúng tại vị trí i.
- Công thức: đoạn kết thúc tại i chỉ có hai khả năng: hoặc chỉ gồm một mình a[i] (bắt đầu lại), hoặc nối thêm a[i] vào đoạn tốt nhất kết thúc tại i - 1. Vậy dp[i] = max(a[i], dp[i - 1] + a[i]). Nói bằng lời: nếu dp[i - 1] là số âm thì mang nó theo chỉ làm Thỏ lỗ thêm, bỏ nó đi và bắt đầu lại.
- Khởi tạo: dp[0] = a[0].
- Đáp án: giá trị lớn nhất trong mảng dp.
i : 0 1 2 3 4 5 6 7
a[i] : -2 1 -3 4 -1 2 1 -5
dp[i] : -2 1 -2 4 3 5 6 1
^ đáp án = 6 (đoạn 4 -1 2 1)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n), dp(n); // long long vì tổng rất lớn
for (int i = 0; i < n; i++) cin >> a[i];
dp[0] = a[0];
long long best = dp[0]; // không đặt 0: có thể toàn số âm
for (int i = 1; i < n; i++) {
dp[i] = max(a[i], dp[i - 1] + a[i]); // làm lại / nối
best = max(best, dp[i]);
}
cout << best;
return 0;
}
Để ý rằng dp[i] chỉ cần dp[i - 1], nên ta có thể thay cả mảng bằng một biến cur (nén bộ nhớ). Tuy vậy, khi mới học em nên viết đủ mảng dp cho dễ nhìn.
So sánh các mẫu DP
| Bài | dp[i] là gì | Công thức | Đáp án |
|---|---|---|---|
| Leo cầu thang (tuần trước) | Số cách lên đến bậc i | dp[i - 1] + dp[i - 2] | dp[n] |
| Dãy con tăng dài nhất | Độ dài dãy tốt nhất kết thúc tại i | max(dp[j] + 1) với j < i, a[j] < a[i] | max(dp) |
| Đoạn có tổng lớn nhất | Tổng tốt nhất của đoạn kết thúc tại i | max(a[i], dp[i - 1] + a[i]) | max(dp) |
Những lỗi hay gặp
- Quên khởi tạo dp[i] = 1 (để 0) nên đáp án bị thiếu 1.
- In dp[n - 1] thay vì giá trị lớn nhất trong mảng dp.
- Nhầm đoạn con (liền nhau) với dãy con (được bỏ qua).
- Nhầm “tăng hẳn” (<) với “không giảm” (<=). Hãy đọc kỹ đề.
- Dùng int khi tổng có thể vượt 2 × 109; đặt best = 0 trong khi tất cả các số đều âm.
Luyện tập
Bài 1. Những bậc đá lên đồi
Gấu Po leo đồi qua n bậc đá xếp thành hàng, bậc thứ i cao a[i]. Po chỉ được bước từ một bậc sang một bậc cao hơn hẳn bậc đang đứng. Po được nhảy qua (bỏ qua) một số bậc nhưng không được quay lại phía sau. Hỏi Po có thể đặt chân lên nhiều nhất bao nhiêu bậc đá?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số bậc đá nhiều nhất Po đặt chân lên. | |
| Test | Input | Output |
| 1 | 8 10 22 9 33 21 50 41 60 | 5 |
| 2 | 5 9 7 5 3 1 | 1 |
Bài 2. Những ngày nắng ấm dần
Thỏ ghi lại nhiệt độ của n ngày liên tiếp. Thỏ muốn chọn ra một số ngày (không cần liền nhau, giữ nguyên thứ tự) sao cho nhiệt độ không giảm, tức là ngày sau nóng hơn hoặc bằng ngày trước. Hỏi Thỏ chọn được nhiều nhất bao nhiêu ngày?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số ngày nhiều nhất. | |
| Test | Input | Output |
| 1 | 7 3 3 1 4 4 2 5 | 5 |
| 2 | 6 2 2 2 1 1 1 | 3 |
Bài 3. Xuống đồi an toàn
Sau khi lên đến đỉnh đồi, Gấu Po đi xuống theo một con đường có n tảng đá, tảng thứ i cao a[i]. Mỗi lần bước, Po chỉ được sang một tảng thấp hơn hẳn tảng đang đứng, được bỏ qua một số tảng nhưng không quay lại phía sau. Hỏi Po bước qua nhiều nhất bao nhiêu tảng đá?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số tảng đá nhiều nhất. | |
| Test | Input | Output |
| 1 | 8 9 4 6 3 5 2 8 1 | 5 |
| 2 | 4 1 2 3 4 | 1 |
Bài 4. Hũ mật ong sinh lời
Thỏ bán mật ong trong n ngày liên tiếp. Ngày thứ i Thỏ lãi a[i] đồng (nếu a[i] âm nghĩa là ngày đó Thỏ bị lỗ). Thỏ muốn chọn một số ngày liên tiếp nhau (ít nhất một ngày) sao cho tổng lãi lớn nhất. Hãy tìm tổng lãi lớn nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng lãi lớn nhất. | |
| Test | Input | Output |
| 1 | 8 -2 1 -3 4 -1 2 1 -5 | 6 |
| 2 | 4 -5 -2 -8 -3 | -2 |
Bài 5. Chuỗi ngày vàng
Với bảng lãi lỗ như bài trước, Thỏ còn muốn biết chuỗi ngày vàng nằm ở đâu. Hãy in tổng lãi lớn nhất và hai số l, r là ngày bắt đầu, ngày kết thúc của chuỗi ngày đó (các ngày đánh số từ 1). Nếu có nhiều chuỗi cùng tổng lớn nhất thì chọn chuỗi có l nhỏ nhất, nếu vẫn còn nhiều chuỗi thì chọn chuỗi có r nhỏ nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Ba số nguyên cách nhau bởi dấu cách: tổng lãi lớn nhất, l và r. | |
| Test | Input | Output |
| 1 | 8 -2 1 -3 4 -1 2 1 -5 | 6 4 7 |
| 2 | 5 3 -3 2 -2 3 | 3 1 1 |
Bài 6. Rời hàng cho đẹp
Hổ xếp n bạn thành một hàng ngang, bạn thứ i cao a[i]. Hổ muốn một số bạn rời khỏi hàng để những bạn còn lại (vẫn giữ nguyên vị trí tương đối) có chiều cao tăng dần hẳn từ trái sang phải. Hỏi ít nhất bao nhiêu bạn phải rời hàng?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 2000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số bạn phải rời hàng ít nhất. | |
| Test | Input | Output |
| 1 | 6 3 1 4 1 5 9 | 2 |
| 2 | 4 1 2 3 4 | 0 |
Bài 7. Đường cà rốt
Thỏ đi qua n gò đất xếp thành hàng. Gò thứ i cao h[i] và có c[i] củ cà rốt. Thỏ chỉ được nhảy từ một gò sang một gò cao hơn hẳn gò đang đứng, được bỏ qua một số gò nhưng không quay lại phía sau. Thỏ có thể bắt đầu và dừng ở gò nào tùy ý, và nhặt hết cà rốt ở mọi gò đã đặt chân. Hỏi Thỏ nhặt được nhiều nhất bao nhiêu củ cà rốt?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 5000). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). Dòng 3: n số nguyên c[i] (1 ≤ c[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Một số nguyên: số củ cà rốt nhiều nhất. | |
| Test | Input | Output |
| 1 | 5 1 3 2 4 5 2 5 6 1 3 | 12 |
| 2 | 4 5 4 3 2 1 2 3 4 | 4 |
Bài 8. Từ điển của Thỏ
Thỏ có một xâu s gồm n chữ cái thường. Thỏ xóa bớt một số chữ cái (các chữ còn lại giữ nguyên thứ tự) để các chữ còn lại xếp theo thứ tự bảng chữ cái, tức là chữ đứng sau phải trùng hoặc đứng sau chữ đứng trước nó trong bảng chữ cái (ví dụ aabdz). Hỏi Thỏ giữ lại được nhiều nhất bao nhiêu chữ?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 5000). Dòng 2: xâu s gồm n chữ cái thường, không có dấu cách. | |
|---|---|---|
| Đầu ra | Một số nguyên: số chữ cái nhiều nhất giữ lại được. | |
| Test | Input | Output |
| 1 | 6 abcabc | 4 |
| 2 | 3 zyx | 1 |
Bài 9. Ngọn núi của Hổ
Hổ có n cột đá xếp thành hàng, cột thứ i cao a[i]. Hổ muốn chọn một số cột (giữ nguyên thứ tự) để dựng thành một ngọn núi: chiều cao tăng hẳn cho đến một cột đỉnh rồi giảm hẳn. Phần đi lên hoặc phần đi xuống có thể chỉ gồm đúng cột đỉnh, nên một cột đơn lẻ cũng là một ngọn núi. Hỏi ngọn núi có nhiều cột nhất là bao nhiêu cột?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 5000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số cột đá nhiều nhất của một ngọn núi. | |
| Test | Input | Output |
| 1 | 9 1 3 5 4 2 6 8 7 4 | 7 |
| 2 | 5 2 2 2 2 2 | 1 |
Bài tập tự luyện
Bài 1. Hai hướng đi
Gấu Po có n cột mốc xếp thành hàng, cột mốc thứ i cao a[i]. Po chọn một hướng đi: hoặc chỉ đi qua các cột mốc cao dần hẳn, hoặc chỉ đi qua các cột mốc thấp dần hẳn (được bỏ qua cột mốc, không quay lại). Hỏi Po đi qua được nhiều nhất bao nhiêu cột mốc?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 2000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số cột mốc nhiều nhất. | |
| Test | Input | Output |
| 1 | 7 5 1 4 2 3 6 0 | 4 |
| 2 | 3 4 4 4 | 1 |
Bài 2. Chuỗi ngày lỗ nặng nhất
Cũng với bảng lãi lỗ của n ngày bán mật ong, lần này Thỏ muốn biết chuỗi ngày liên tiếp (ít nhất một ngày) nào lỗ nặng nhất, tức là có tổng nhỏ nhất. Hãy in ra tổng nhỏ nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng nhỏ nhất của một chuỗi ngày liên tiếp. | |
| Test | Input | Output |
| 1 | 7 3 -4 2 -5 -1 6 -2 | -8 |
| 2 | 3 4 1 6 | 1 |
Bài 3. Đi hội chợ ít nhất hai ngày
Thỏ đi bán mật ong ở hội chợ. Theo luật của hội chợ, Thỏ phải tham gia ít nhất hai ngày liên tiếp. Ngày thứ i Thỏ lãi a[i] đồng (có thể âm nếu bị lỗ). Hãy tìm tổng lãi lớn nhất khi Thỏ chọn một chuỗi từ hai ngày liên tiếp trở lên.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng lãi lớn nhất. | |
| Test | Input | Output |
| 1 | 5 -1 5 -2 4 -10 | 7 |
| 2 | 3 -5 -4 -3 | -7 |
Bài 4. Bước nhảy vừa chân
Gấu Po có đôi chân ngắn nên mỗi lần bước chỉ lên được bậc đá cao hơn bậc đang đứng, nhưng cao hơn không quá D. Có n bậc đá xếp thành hàng, bậc thứ i cao a[i]. Po được bỏ qua bậc đá nhưng không quay lại phía sau. Hỏi Po đặt chân lên được nhiều nhất bao nhiêu bậc?
| Đầu vào | Dòng 1: hai số nguyên n, D (1 ≤ n ≤ 2000, 1 ≤ D ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số bậc đá nhiều nhất. | |
| Test | Input | Output |
| 1 | 7 5 1 2 9 3 10 4 5 | 5 |
| 2 | 4 1 1 3 5 7 | 1 |
Bài 5. In dãy bậc đá (không bắt buộc)
Cho n bậc đá như bài “Những bậc đá lên đồi”. Lần này Gấu Po không chỉ muốn biết số bậc nhiều nhất mà còn muốn biết chiều cao của các bậc đá đó, theo thứ tự đã đi qua. Nếu có nhiều cách chọn, in một cách bất kỳ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 2000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Dòng 1: số bậc đá nhiều nhất. Dòng 2: chiều cao các bậc đá đó theo thứ tự đi qua, cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 1 | 8 10 22 9 33 21 50 41 60 | 5 10 22 33 50 60 |
| 2 | 5 5 4 3 2 1 | 1 5 |
Bài 6. Búp bê Nga lồng nhau
Hổ có n chiếc hộp, hộp thứ i có chiều rộng w[i] và chiều cao h[i]. Hộp A đặt vừa vào bên trong hộp B nếu cả chiều rộng và chiều cao của A đều nhỏ hơn hẳn của B (không được xoay hộp). Hổ muốn lồng các hộp vào nhau thành một chuỗi “hộp trong hộp” dài nhất. Các hộp được cho theo thứ tự bất kỳ, Hổ lấy hộp nào trước cũng được.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 3000). n dòng tiếp theo: mỗi dòng gồm hai số nguyên w[i], h[i] (1 ≤ w[i], h[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số hộp nhiều nhất trong một chuỗi lồng nhau. | |
| Test | Input | Output |
| 1 | 5 5 4 6 4 3 2 6 7 2 1 | 4 |
| 2 | 3 1 1 1 2 2 1 | 1 |
Bài 7. Hai vụ mùa
Thỏ trồng cà rốt hai vụ. Mỗi vụ là một chuỗi ngày liên tiếp (ít nhất một ngày), hai vụ không được trùng ngày nào và vụ thứ nhất phải kết thúc trước khi vụ thứ hai bắt đầu. Ngày thứ i cho thu hoạch a[i] củ (có thể âm nếu bị sâu ăn). Hãy tìm tổng thu hoạch lớn nhất của hai vụ.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng thu hoạch lớn nhất của hai vụ. | |
| Test | Input | Output |
| 1 | 8 2 -1 2 -5 3 4 -2 1 | 10 |
| 2 | 2 -3 -4 | -7 |
Bài 8. Vòng đua cà rốt (không bắt buộc)
n hố cà rốt xếp quanh một vòng tròn, hố thứ n nằm cạnh hố thứ 1. Hố thứ i có a[i] củ (có thể âm nếu có cạm bẫy). Gấu Po chọn một dãy hố liền nhau trên vòng (có thể đi qua hố n rồi sang hố 1), ít nhất một hố và mỗi hố chỉ đi qua một lần. Hãy tìm tổng lớn nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng lớn nhất. | |
| Test | Input | Output |
| 1 | 6 8 -5 -1 2 -9 6 | 14 |
| 2 | 3 -3 -1 -2 | -1 |
Bài 9. Thử thách: Dãy con tăng siêu tốc (không bắt buộc)
Cho n bậc đá như bài “Những bậc đá lên đồi”, nhưng lần này n rất lớn nên cách hai vòng for không kịp. Hãy tìm độ dài dãy con tăng dài nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: độ dài dãy con tăng dài nhất. | |
| Test | Input | Output |
| 1 | 10 2 8 3 9 4 10 5 11 6 12 | 6 |
| 2 | 6 6 5 4 3 2 1 | 1 |
- Gợi ý chung: Khi con bị tắc, hãy hỏi lần lượt từng câu: (1) “Nếu bắt buộc dãy (hoặc đoạn) kết thúc đúng ở vị trí i thì dp[i] nghĩa là gì?”; (2) “Vị trí i có thể nối vào sau những vị trí nào?”; (3) “Đáp án nằm ở dp[n - 1] hay ở chỗ khác?”. Ba lỗi hay gặp nhất là quên dp[i] = 1 ban đầu, đặt best = 0 khi toàn số âm, và dùng int khi tổng vượt 2 × 109.
Gợi ý cho các bài khó: Bài “Ngọn núi của Hổ”: hãy hỏi con “nếu đỉnh núi là cột i thì phần đi lên và phần đi xuống mỗi phần dài nhiều nhất bao nhiêu?”, rồi dùng thêm một mảng dp tính từ phải sang trái. Bài “Búp bê Nga lồng nhau”: sắp xếp các hộp theo chiều rộng bằng pair (tuần 11), rồi làm như dãy con tăng. Bài “Hai vụ mùa”: tính trước cho mỗi vị trí i đoạn tốt nhất nằm hết trong 1..i và đoạn tốt nhất nằm hết trong i..n. Bài “Vòng đua cà rốt”: đoạn vắt qua chỗ nối hố n và hố 1 là phần còn lại của đoạn nào trên dãy thẳng? Bài “Dãy con tăng siêu tốc”: giữ một mảng d, trong đó d[k] là giá trị cuối cùng nhỏ nhất của một dãy tăng có k + 1 phần tử; với mỗi số mới x, lower_bound (tuần 12) cho biết x nên ghi đè vào ô nào của d.