Dự án
Đề bài
Có $n$ dự án bạn có thể tham gia. Đối với mỗi dự án, bạn biết ngày bắt đầu và ngày kết thúc của nó và số tiền bạn sẽ nhận được làm phần thưởng. Bạn chỉ có thể tham dự một dự án trong một ngày.
Số tiền tối đa mà bạn có thể kiếm được là bao nhiêu?
Input
- Dòng đầu vào đầu tiên chứa một số nguyên $n$: số lượng dự án.
- Sau đó, có $n$ dòng. Mỗi dòng như vậy có ba số nguyên $a_i$, $b_i$ và $p_i$: ngày bắt đầu, ngày kết thúc và phần thưởng.
Output
- In một số nguyên: số tiền tối đa mà bạn có thể kiếm được.
Constraints
- $1 \le n \le 2 \cdot 10^5$
- $1 \le a_i \le b_i \le 10^9$
- $1 \le p_i \le 10^9$
4
2 4 4
3 6 6
6 8 2
5 7 37Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Tóm tắt đề bài
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau: cho bạn $n$ dự án. Đối với mỗi dự án, bạn biết ngày bắt đầu và kết thúc của nó và số tiền bạn nhận được khi làm dự án đó. Bạn chỉ có thể tham gia một dự án trong một ngày; tức nếu dự án mình làm kết thúc ở ngày 6 thì dự án tiếp theo mình nhận phải bắt đầu từ ngày 7 đổ lên chứ không được nhận từ ngày 6. Hỏi bạn có thể kiếm được tối đa là bao nhiêu tiền?
- Dòng đầu tiên là số nguyên dương $n$ là số dự án ($1 \le n \le 2 \times 10^5$).
- Sau đó có $n$ dòng. Dòng thứ $i$ có 3 số nguyên là $a$, $b$ và $p$: ngày bắt đầu, ngày kết thúc và phần thưởng ($1 \le a \le b \le 10^9$; $1 \le p \le 10^9$).
- In ra một số nguyên là số tiền tối đa mà bạn có thể kiếm được.
Giải thích ví dụ: ở đây ta làm dự án đầu tiên và dự án cuối cùng. Số tiền ta nhận được là: 4 + 3 = 7.
Ta không thể làm dự án thứ 2 và thứ 3 vì dự án thứ 2 kết thúc ở ngày 6; dự án thứ 3 bắt đầu vào ngày 6 nên không thể chọn 2 dự án này. Dự án thứ 3 phải bắt đầu từ ngày 7 đổ đi thì ta mới chọn được dự án thứ 2 và dự án thứ 3.
Bước chuẩn bị: sắp xếp các dự án
Đầu tiên, để làm được bài này thì ta cần sắp xếp lại các dự án theo một thứ tự là ngày bắt đầu hoặc ngày kết thúc. Nếu ta làm vậy thì sẽ dễ dàng quản lý hơn; ví dụ ta sắp xếp các dự án tăng dần theo ngày kết thúc. Khi ta chọn làm dự án thứ $i$, thì dự án tiếp theo ta chọn là dự án thứ $j$ với ($j > i$); điều kiện chọn được là chỉ cần dự án thứ $j$ có thời gian bắt đầu > thời gian kết thúc của dự án $i$ là ta chọn được. Vì ta đảm bảo là thời gian kết thúc của các dự án tăng dần, nên dự án $j$ ($j > i$) mà có thời gian bắt đầu > thời gian kết thúc dự án $i$ là ta đảm bảo dự án đó không bị trùng. Các bạn có thể vẽ nó lên một trục số, nó sẽ dễ hình dung hơn. Ví dụ như sau nè:
Ta thấy khi thời gian kết thúc ($b$) được sắp xếp tăng dần, thì với a[j] > b[i] thì chắc chắn 2 đoạn đó không trùng; tức là ta có thể thực hiện công việc $j$ mà không lo bị trùng.
Vậy với $j < i$ thì sao? Lúc này ta vẫn sắp xếp dãy tăng dần theo thời gian kết thúc nha. Ta thấy lúc này ta chỉ cần thời gian kết thúc của dự án $j$ < thời gian bắt đầu của dự án $i$ là ta có thể chọn được dự án $j$. Ví dụ trên trục số như sau nhé:
Ta thấy vì được xếp tăng dần theo thời gian kết thúc, nên nếu dự án $j$ ($j < i$) mà có thời gian kết thúc (b[j]) < thời gian bắt đầu dự án $i$ (a[i]) thì ta đảm bảo 2 đoạn không trùng nhau; tức là ta có thể thực hiện công việc $j$ mà không lo bị trùng.
Bạn nào mà thích thì cũng có thể sắp xếp tăng dần theo thời gian bắt đầu nha; cách tư duy thì cũng khá giống trên, các bạn cứ vẽ ra trục số thì sẽ dễ hình dung hơn. Tại bài này thì mình sẽ sắp xếp các dự án tăng dần theo thời gian kết thúc nha. Với ví dụ của đề, sau khi sắp xếp ta có:
| i (sau khi sắp xếp) | a (bắt đầu) | b (kết thúc) | p (tiền) |
|---|---|---|---|
| 1 | 2 | 4 | 4 |
| 2 | 3 | 6 | 6 |
| 3 | 5 | 7 | 3 |
| 4 | 6 | 8 | 2 |
Lưu trữ dự án bằng struct
Giờ ta cần biết làm sao để sắp xếp các dự án tăng dần theo thời gian kết thúc một cách tiện nhất. Nếu ta mà dùng 3 mảng a, b, p thì khi sắp xếp mảng b tăng dần thì mảng a và p lại không được đi theo cùng. Để xử lý vấn đề này, ta sẽ tạo ra một kiểu dữ liệu mới; kiểu dữ liệu này bên trong có 3 biến con là a, b và p tương ứng với thời gian bắt đầu, kết thúc và lợi nhuận của dự án. Ta có thể dễ dàng làm điều này bằng cách sử dụng struct:
struct Data {
int a, b;
long long p;
};Ta tạo một kiểu dữ liệu mới là Data; bên trong có 3 biến là a, b và p. Đặc biệt ở đây là ta để biến p thuộc kiểu dữ liệu long long là vì tối đa ta có $2 \times 10^5$ dự án, mỗi dự án thì lợi nhuận có thể lên tới $10^9$ nên lợi nhuận tối đa ta thu được có thể lên tới $10^9 \times 2 \times 10^5 = 2 \times 10^{14}$ (vượt qua giới hạn của kiểu int). Chính vì vậy nên ta xài kiểu dữ liệu long long nha.
Ta sẽ tạo một mảng Data projects để lưu trữ các dự án, với projects[i] là dự án thứ $i$. Cách để truy cập thời gian bắt đầu của dự án $i$ chính là: projects[i].a; tương tự với thời gian kết thúc và lợi nhuận là: projects[i].b và projects[i].p. Để đọc vào dự án $i$ thì ta sẽ làm như sau:
cin >> projects[i].a >> projects[i].b >> projects[i].p;Sắp xếp bằng biểu thức lambda hoặc hàm comp
Cuối cùng là việc sắp xếp các dự án này tăng dần theo thời gian kết thúc. Để làm được điều này ta có thể dùng hàm sort + thêm dùng biểu thức lambda. Dành cho bạn nào chưa biết thì các bạn có thể tham khảo ở đây: Lambda expression in C++ (GeeksforGeeks). Sau đây sẽ là code của mình để sắp xếp các dự án tăng dần theo thời gian kết thúc:
sort(projects + 1, projects + n + 1, [](const Data &a, const Data &b) -> bool {
return a.b < b.b;
});(Vì mình lưu từ projects[1] đến projects[n] nên ta sẽ sắp xếp từ projects + 1 đến projects + n + 1.)
Bạn nào mà không biết thì ta hoàn toàn có thể xây dựng một hàm comp (hàm giúp ta kiểm soát việc sắp xếp theo ý muốn) rồi truyền vào cũng được. Đầu tiên ta tạo một hàm comp:
bool comp(const Data &a, const Data &b) {
return a.b < b.b;
}Kiểu trả về chính là bool; 2 biến truyền vào sẽ theo kiểu Data; ta thêm tham chiếu (&) để truy cập trực tiếp vào biến mà không phải copy. Để tránh hàm comp thay đổi 2 biến được tham chiếu, ta sẽ thêm const vào đằng trước để tránh nó bị thay đổi trong hàm comp. Trong hàm comp thì ta cần sắp xếp tăng dần theo thời gian kết thúc nên chỉ cần: return a.b < b.b;. Để sort thì ta làm như sau:
sort(projects + 1, projects + n + 1, comp);Ta truyền vào hàm comp là nó sẽ sắp xếp dựa trên hàm comp của ta (tức sắp xếp tăng dần theo thời gian kết thúc dự án).
upper_bound hoặc lower_bound thì ta nên xài cách tạo hàm comp; vì ta dùng nhiều lần nên tạo hàm comp để dùng thì code sẽ gọn hơn.7/14Cách 1: vét cạn bằng đệ quy
Giải quyết xong vấn đề lưu trữ và sắp xếp thì giờ ta sẽ đến với cách làm đơn giản nhất của bài này. Đó chính là vét cạn, tức ta thử mọi trường hợp có thể đó. Ta sẽ xây dựng hàm đệ quy như sau:
Gọi hàm long long Try(int n) sẽ trả về số tiền tối đa ta có thể kiếm được từ $n$ dự án đầu tiên (các dự án đã được ta sắp xếp tăng dần theo thứ tự ngày kết thúc rồi nha).
Điều kiện dừng:
- Khi ta không còn dự án nào ($n = 0$). Lúc này hiển nhiên khi ta không còn dự án nào thì số tiền ta kiếm được sẽ = 0. Vậy ta kiểm tra nếu
n == 0thì tareturn 0. - Khi ta chỉ còn 1 dự án đầu tiên ($n = 1$). Lúc này số tiền nhiều nhất ta kiếm được chính là lợi nhuận của dự án đầu tiên. Vì lúc này ta chỉ có một dự án duy nhất thì dĩ nhiên ta sẽ làm rồi; từ đó số tiền ta kiếm được chính là
projects[1].p. Vậy ta kiểm tra nếun == 1thì tareturn projects[1].p.
Xử lý chạy: ta có 2 trường hợp sau:
- Ta không làm dự án thứ $n$. Suy ra: số tiền tối đa ta có thể kiếm được từ $n$ dự án đầu tiên ở trường hợp này (không làm dự án $n$) sẽ = số tiền tối đa ta có thể kiếm được từ $n - 1$ dự án đầu tiên. Vì ta đang xét $n$ dự án đầu tiên, ta không chọn dự án thứ $n$ thì đương nhiên ta còn $n - 1$ dự án đầu tiên rồi. Viết lại thì ta có: số tiền tối đa khi ta không làm dự án thứ $n$ =
Try(n - 1). - Ta có làm dự án thứ $n$. Lúc này đương nhiên là ta sẽ có được lợi nhuận từ việc làm dự án thứ $n$ rồi; vì ta làm nó mà. Ta sẽ nhận được
projects[n].ptiền. Bây giờ ta cần tìm dự án có thứ tự lớn nhất và thời gian kết thúc < thời gian bắt đầu của dự án $n$. Tại sao ta lại cần làm vậy?
Để cho các bạn dễ hình dung thì ta gọi dự án ta chọn là dự án $i$ đi. Như đã phân tích ở phần lý do ta sắp xếp các dự án tăng dần theo thời gian kết thúc, thì sau khi ta chọn dự án $i$, gọi dự án tiếp theo ta xét là dự án $j$ với ($j < i$). Vì ta đang xét $i$ dự án đầu tiên thôi nên dự án tiếp theo ta xét phải nhỏ hơn $i$. Để chọn được dự án $j$ thì ta phải thoả mãn thời gian kết thúc của nó < thời gian bắt đầu của dự án $i$ (mình đã lý giải ở trên). Và ta cần $j$ lớn nhất có thể là vì càng xét nhiều dự án thì ta càng có thể được nhiều tiền mà. Ví dụ: số tiền tối đa ta kiếm được từ 4 dự án đầu tiên chắc chắn ≥ số tiền tối đa ta kiếm được từ 3 hay 2 hay 1 dự án đầu tiên; vậy theo tư tưởng tham lam (ở đây là càng nhiều càng tốt) thì ta sẽ lấy $j$ lớn nhất có thể.
Vậy ta sẽ tạo ra một hàm tìm ra $j$ từ $i$. Hàm này sẽ tìm ra vị trí $j$ lớn nhất có thể, thoả mãn ($j < i$) và (thời gian kết thúc của dự án $j$ < thời gian bắt đầu của dự án $i$). Viết lại chính là: ($j < i$) và (projects[j].b < projects[i].a). Ý tưởng của ta sẽ là duyệt một vòng for($j$) chạy từ $i - 1$ về tới 1; ta sẽ check projects[j].b < projects[i].a; nếu thoả mãn thì ta trả về $j$ luôn vì ta đang duyệt ngược nên đó chính là $j$ lớn nhất. Ngược lại nếu hết vòng for rồi mà vẫn không trả về, tức không tồn tại giá trị $j$ thoả mãn, thì ta trả về $j = 0$ (có nghĩa là không có dự án nào có thời gian kết thúc < thời gian bắt đầu của dự án $i$). Mình thực hiện như sau:
int findJ(int i) {
for(int j = i - 1; j >= 1; --j) {
if(projects[j].b < projects[i].a) {
return j;
}
}
return 0;
}Quay trở lại trường hợp ta có làm dự án $n$: số tiền tối đa ta kiếm được từ trường hợp này sẽ là số tiền kiếm được từ dự án $n$ + số tiền tối đa ta kiếm được từ findJ(n) dự án đầu tiên. Vì dự án thứ findJ(n) sẽ thoả mãn có thời gian kết thúc < thời gian bắt đầu dự án $n$ và có số thứ tự lớn nhất có thể (số thứ tự càng lớn, ta càng xét được nhiều dự án hơn, suy ra ta càng có thể kiếm được nhiều tiền hơn). Viết lại: số tiền tối đa khi ta có làm dự án $n$ = projects[n].p + Try(findJ(n)).
Từ 2 trường hợp trên ta có: số tiền tối đa ta có thể kiếm được từ $n$ dự án đầu tiên sẽ = max(trường hợp 1, trường hợp 2):
Em nhập các dự án (mỗi dự án 3 số a b p, các dự án cách nhau dấu phẩy) rồi bấm Tiếp để xem từng bước: sắp xếp theo ngày kết thúc, rồi với mỗi dự án $i$ tìm $j$ và chọn phương án tốt hơn giữa "không làm" và "làm" dự án $i$:
Sau đây là Source Code của mình về ý tưởng trên cho bạn nào cần tham khảo nha:
Xem code cách 1 (vét cạn)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
struct Data {
int a, b;
ll p;
};
const int N = 2 * (int)1e5 + 5;
Data projects[N];
int findJ(int i) {
for(int j = i - 1; j >= 1; --j) {
if(projects[j].b < projects[i].a) {
return j;
}
}
return 0;
}
ll Try(int n) {
if(n == 0) {
return 0;
}
if(n == 1) {
return projects[1].p;
}
return max(Try(n - 1), projects[n].p + Try(findJ(n)));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> projects[i].a >> projects[i].b >> projects[i].p;
}
sort(projects + 1, projects + n + 1, [](const Data &a, const Data &b) -> bool {
return a.b < b.b;
});
cout << Try(n);
return 0;
}Giải thích một số chỗ trong code ở trên:
- 2 dòng đầu tiên của hàm main (
ios::sync_with_stdio(0); cin.tie(0);) sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta nên sử dụng 2 dòng trên. Trong bài này thì đầu vào có thể lên tới $6 \times 10^5$ số, nên các bạn nên thêm 2 dòng trên vào nha. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé. cout << Try(n);Đáp án của bài toán dĩ nhiên là số tiền tối đa ta có thể kiếm được từ $n$ dự án đầu tiên nên ta sẽ in ra kết quả của hàmTry(n).
Đánh giá độ phức tạp của cách làm trên:
- Độ phức tạp không gian (Space Complexity): $O(N)$, vì ta xài một mảng
projects. - Độ phức tạp thời gian (Time Complexity): $O(n \times 2^n)$. Với mỗi dự án thì ta sẽ có 2 lựa chọn là làm hoặc không làm; từ đó với $n$ dự án thì ta sẽ có thể có tổng cộng $2^n$ cách chọn. Và trong mỗi lần xét trường hợp có làm dự án thứ $n$ thì ta phải xài hàm
findJ; hàm này có độ phức tạp là $O(n)$. Từ 2 điều trên, độ phức tạp thời gian của ta sẽ là $O(n \times 2^n)$.
13/14Cách 2: đệ quy có nhớ (quy hoạch động top-down)
Với code trên ta hoàn toàn có thể cải tiến thành quy hoạch động top-down, hay còn gọi là đệ quy có nhớ. Lý do code phần trên của ta chạy lâu chính là vì nếu ta đã tính 1 vấn đề rồi mà lần sau có gặp lại thì ta vẫn phải đi tính lại nó; việc tính đi tính lại này khiến ta tốn rất nhiều thời gian. Từ đó tư tưởng của thuật toán là dùng 1 kiểu dữ liệu (có thể là mảng, vector, map, …) để lưu trữ những kết quả ta đã tính toán; và khi ta gặp những vấn đề mà ta đã tính thì ta chỉ việc trả về kết quả mà thôi (không phải tính lại nữa). Ta sẽ làm như sau:
- Xác định mỗi lần gọi đệ quy thì có những tham số nào có thể thay đổi: trong code vét cạn của ta, cụ thể là hàm
Try()chỉ có 1 tham số đầu vào là $n$. Và cũng chỉ có nó là thay đổi ở mỗi lần ta gọi đệ quy. Vậy ta sẽ tạo ra một mảng 1 chiềuF, với phần tửF[n]sẽ lưu trữ kết quả của hàmTry(n). - Xác định giới hạn của các tham số có thể thay đổi: ta thấy $n$ tối đa có thể = $2 \times 10^5$. Vậy ta sẽ tạo ra một mảng 1 chiều
F[2 * 10^5 + 5]; mình thường cộng thêm 5 vào để thừa ra vài phần tử (tránh ta truy cập vào phần tử không có trong mảng, từ đó bị lỗi chương trình). - Xác định giá trị không thể trả về của hàm: ta thấy hàm không thể trả về giá trị âm, cụ thể hơn hàm không thể trả về giá trị −1. Chính vì vậy nên ta sẽ lấp đầy mảng
F= giá trị −1, để sau mục điều kiện dừng ta kiểm tra nếuF[n] != -1thì có nghĩa ta đã tínhTry(n)và lưu kết quả vàoF[n]. Lúc này ta chỉ cần trả vềF[n]là được. Ngược lại, nếuF[n] = -1thì chứng tỏ ta chưa tínhTry(n). Ta sẽ đi tínhTry(n)như bình thường, cuối cùng ta chỉ việc gán kết quả vàoF[n]rồi trả về là được.
Sau đây là Source Code của mình về ý tưởng trên cho bạn nào cần tham khảo nha:
Xem code cách 2 (đệ quy có nhớ)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
struct Data {
int a, b;
ll p;
};
const int N = 2 * (int)1e5 + 5;
Data projects[N];
int findJ(int i) {
for(int j = i - 1; j >= 1; --j) {
if(projects[j].b < projects[i].a) {
return j;
}
}
return 0;
}
ll f[N];
ll Try(int n) {
if(n == 0) {
return 0;
}
if(n == 1) {
return projects[1].p;
}
if(f[n] != -1) {
return f[n];
}
return f[n] = max(Try(n - 1), projects[n].p + Try(findJ(n)));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> projects[i].a >> projects[i].b >> projects[i].p;
}
sort(projects + 1, projects + n + 1, [](const Data &a, const Data &b) -> bool {
return a.b < b.b;
});
fill(f, f + n + 1, -1);
cout << Try(n);
return 0;
}Giải thích một số chỗ trong cách làm trên:
return f[n] = max(Try(n - 1), projects[n].p + Try(findJ(n)));Ở đây chính là ta gánf[n] = max(Try(n - 1), projects[n].p + Try(findJ(n))). Sau đó ta returnf[n]đó.fill(f, f + n + 1, -1);Đây chính là ta lấp đầy mảngf= −1. Bạn nào mà không biết hàmfillthì xài vòngfor()cũng được nha; độ phức tạp thời gian của nó là như nhau thôi.
Đánh giá độ phức tạp của cách làm trên:
- Độ phức tạp không gian (Space Complexity): $O(N)$. Thực chất chính là $O(2 \times N)$ vì ta xài 2 mảng là
projectsvàf; nhưng theo quy tắc Big O thì nó sẽ là $O(N)$. - Độ phức tạp thời gian (Time Complexity): $O(n^2)$. Vì trong trường hợp tệ nhất là ta phải lấp đầy mảng
f; và trong mỗi lần xét trường hợp có làm dự án thứ $n$ thì ta phải xài hàmfindJ, hàm này có độ phức tạp là $O(n)$. Nói cách khác, để tạo ra mỗi phần tử trong mảngfthì ta cần $n$ phép tính. Vậy ta sẽ có độ phức tạp thời gian là $O(n \times n) = O(n^2)$.
ACCách 3: tối ưu findJ bằng tìm kiếm nhị phân
Nhìn vào cách làm trên, ta thấy điều gì khiến code ta chưa được tối ưu? Ta thấy đó chính là hàm findJ(); hàm này có độ phức tạp thời gian là $O(n)$. Vậy ta có thể cải tiến nó không? Câu trả lời là có; ta có thể cải tiến nó dựa vào thuật toán tìm kiếm nhị phân. Trước hết các bạn cần nắm rõ 2 hàm là lower_bound và upper_bound trong C++. Dành cho bạn nào chưa biết thì mình tiến cử 2 link này, mình thấy nó khá đầy đủ: lower_bound và upper_bound.
Hiểu nhanh về lower_bound
Bài này ta sẽ cần xài tới lower_bound; hiểu đơn giản nó sẽ là thế này:
1. Cú pháp: lower_bound(vị trí bắt đầu tìm, vị trí kết thúc tìm, phần tử cần tìm). Nếu mảng hoặc vector của ta mà được sắp xếp tăng dần theo hàm comp thì ta phải truyền hàm comp vào nha; tức ta sẽ gọi: lower_bound(vị trí bắt đầu tìm, vị trí kết thúc tìm, phần tử cần tìm, hàm comp).
2. Kết quả trả về: trả về một con trỏ sẽ trỏ đến ngay tại phần tử đầu tiên trong đoạn từ vị trí bắt đầu tìm đến trước vị trí kết thúc tìm mà tại đó phần tử đó ≥ phần tử cần tìm. Nếu không tồn tại phần tử ≥ phần tử cần tìm thì nó trả về con trỏ sẽ trỏ đến phần tử tại vị trí kết thúc tìm.
first và vị trí kết thúc tìm là last thì nó sẽ tìm kiếm trong khoảng [first, last). Có nghĩa là nó sẽ tìm kiếm từ first cho tới last - 1; nếu không có giá trị nào thoả mãn thì nó trả về last (tức trả về con trỏ là vị trí kết thúc tìm).3. Ví dụ: mảng của ta được sắp xếp là: a = {1, 3, 5, 6, 8, 9, 11} (mảng lưu từ index 0).
4. Cách để lấy index (vị trí) của giá trị mà con trỏ trỏ đến: để tính được index chính là ta đi tính khoảng cách từ con trỏ tìm thấy đến con trỏ đầu mảng. Tức index = con trỏ tìm thấy − con trỏ đầu mảng. Ở mảng thì con trỏ đầu mảng chính là tên của mảng. Từ đó theo ví dụ trên thì index sẽ là: int idx = lower_bound(a, a + 5, 6) - a; và idx sẽ = 3.
5. Mở rộng: ta thấy ta có thể dễ dàng tìm ra được index của giá trị đầu tiên ≥ giá trị cần tìm. Nếu ta giảm index đi một đơn vị (idx--) thì ta sẽ có được index của giá trị cuối cùng < giá trị cần tìm. Vì đằng trước của giá trị đầu tiên ≥ cần tìm sẽ là giá trị cuối cùng < cái cần tìm rồi. Nhìn vào ví dụ trên, ta thấy idx mà giảm đi một đơn vị thì sẽ thành 2; a[2] (= 5) chính là giá trị cuối cùng < giá trị cần tìm (= 6), chính là ô màu cam.
Áp dụng vào hàm findJ
Quay trở lại vấn đề ta đang cần giải quyết. Ta thấy mảng projects của ta được sắp xếp tăng dần theo thời gian kết thúc của các dự án. Giờ ta đang cần tìm dự án $j$ có số thứ tự lớn nhất ($j$ max) thoả mãn ($j < i$) và có thời gian kết thúc nhỏ hơn thời gian bắt đầu của dự án $i$. Nói cách khác, ta đang cần tìm dự án $j$ cuối cùng thoả mãn ($j < i$) và có thời gian kết thúc nhỏ hơn thời gian bắt đầu của dự án $i$. Vì cái cuối cùng chính là cái lớn nhất.
Các bạn thấy nó giống phần mở rộng mà ta có thể suy ra từ hàm lower_bound rồi chứ. Dự án có index $j$ đó là dự án cuối cùng có thời gian kết thúc < giá trị cần tìm (thời gian bắt đầu dự án $i$) trong đoạn từ 1 tới $i - 1$ ($j < i$); xong rồi mảng lại còn được sắp xếp tăng dần theo thời gian kết thúc dự án nữa. Vậy giờ ta sẽ coi thời gian bắt đầu dự án $i$ là giá trị cần tìm. Từ đó nhờ hàm lower_bound ta có thể tìm được index của dự án đầu tiên có thời gian kết thúc ≥ giá trị cần tìm. Sau đó ta giảm index đi 1 đơn vị là ta đã có được index của dự án cuối cùng có thời gian kết thúc < giá trị cần tìm rồi. Ta sẽ làm như sau:
bool comp(const Data &a, const Data &b) {
return a.b < b.b;
}
const int N = 2 * (int)1e5 + 5;
Data projects[N];
int findJ(int i) {
Data x;
x.b = projects[i].a;
int j = (lower_bound(projects + 1, projects + i, x, comp) - projects) - 1;
return j;
}Giải thích trong code ở trên:
- Tại sao lại phải có hàm comp? Như đã nói ở phần xài lambda hay là xài hàm
compthì khi ta phải sort lẫn xài hàmlower_boundhayupper_bound(tức là ta phải xài nhiều lần) thì ta nên viết hàmcompcho code gọn. Nếu mảng được sắp xếp tăng dần theo hàmcompthì để hàmlower_boundhoặcupper_boundtrả về đúng tác dụng của nó thì ta cũng phải truyền vào đó hàmcomp. - Lý do ta tạo biến
Data xvà gánx.b = projects[i].a;Hàmcompcủa ta có đầu vào là kiểu dữ liệuDatavà so sánh thời gian kết thúc của các dự án. Từ đó giá trị cần tìm (thời gian bắt đầu dự án $i$) cũng phải thuộc kiểu dữ liệuData, và giá trị cần tìm phải nằm ở thời gian kết thúc thuộc kiểu dữ liệuData. Nghe sẽ khá khó hiểu; nhưng các bạn thấy giữa 2 biến thuộc kiểu dữ liệuData, hàmcompchỉ so sánh giá trị kết thúc (tức giá trịb) của bọn nó; vậy ta phải gán cái giá trịb= cái giá trị ta cần tìm (tức thời gian bắt đầu dự án $i$). Suy ra ta tạo một biếnDatatên làx; ta gánx.b= giá trị cần tìm (nó =projects[i].a). int j = (lower_bound(projects + 1, projects + i, x, comp) - projects) - 1;Vì ta lưu các giá trị trong mảngprojectstừ 1 nên hàmlower_boundcủa ta sẽ bắt đầu tìm kiếm từprojects + 1(tức từ index 1) tớiprojects + i(tức tới index $i - 1$).lower_bound(projects + 1, projects + i, x, comp) - projectssẽ cho ta index của dự án đầu tiên có thời gian kết thúc ≥ thời gian bắt đầu dự án $i$. Ta chỉ cần lùi lại một đơn vị (−1) thì ta sẽ có index dự án cuối cùng có thời gian kết thúc < thời gian bắt đầu dự án $i$. Hay chính là giá trị $j$ lớn nhất thoả mãn ($j < i$) và cóprojects[j].b < projects[i].a.
Dành cho bạn nào thắc mắc tại 1 số trường hợp đặc biệt thì liệu hàm findJ của ta có còn đúng không:
- Nếu không tồn tại dự án nào trong khoảng từ 1 tới $i - 1$ có thời gian kết thúc < thời gian bắt đầu dự án $i$ thì sao? Ta thấy trường hợp đó sẽ xảy ra khi
lower_bound(...) - projects = 1, tức dự án 1 đã có thời gian kết thúc ≥ thời gian bắt đầu dự án $i$. Lúc đó $j = 1 - 1 = 0$. Suy ra kết quả của ta vẫn đúng: khi không tồn tại dự án $j$ nào thì $j$ sẽ = 0. - Nếu mọi dự án trong khoảng từ 1 tới $i - 1$ đều có thời gian kết thúc < thời gian bắt đầu dự án $i$ (không có dự án nào ≥) thì sao? Ta thấy trường hợp đó sẽ xảy ra khi
lower_bound(...) - projects = i. Lúc đó $j = i - 1$. Suy ra kết quả của ta vẫn đúng; tại trường hợp này thì dự án $i - 1$ chính là dự án có số thứ tự lớn nhất trong khoảng từ 1 tới $i - 1$ mà có thời gian kết thúc < thời gian bắt đầu dự án $i$.
Sau đây là Source Code của mình về ý tưởng trên cho bạn nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
struct Data {
int a, b;
ll p;
};
bool comp(const Data &a, const Data &b) {
return a.b < b.b;
}
const int N = 2 * (int)1e5 + 5;
Data projects[N];
int findJ(int i) {
Data x;
x.b = projects[i].a;
int j = (lower_bound(projects + 1, projects + i, x, comp) - projects) - 1;
return j;
}
ll f[N];
ll Try(int n) {
if(n == 0) {
return 0;
}
if(n == 1) {
return projects[1].p;
}
if(f[n] != -1) {
return f[n];
}
return f[n] = max(Try(n - 1), projects[n].p + Try(findJ(n)));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> projects[i].a >> projects[i].b >> projects[i].p;
}
sort(projects + 1, projects + n + 1, comp);
fill(f, f + n + 1, -1);
cout << Try(n);
return 0;
}Giải thích một số chỗ trong code ở trên: sort(projects + 1, projects + n + 1, comp); Ở đây vì ta đã xây dựng hàm comp rồi nên ta chỉ cần truyền hàm comp vào thôi chứ không cần sử dụng biểu thức lambda nữa. Bạn nào mà không thích dùng hàm comp thì thay thế những chỗ xài hàm comp bằng biểu thức lambda đều được nha; miễn làm sao ở cả hàm sort và hàm lower_bound có biểu thức lambda giống nhau thì kết quả của ta vẫn đúng nha. Ví dụ nếu ta xài biểu thức lambda để truyền vào lower_bound:
lower_bound(projects + 1, projects + i, x, [](const Data &a, const Data &b) -> bool {
return a.b < b.b;
});Đánh giá độ phức tạp của cách làm trên:
- Độ phức tạp không gian (Space Complexity): $O(N)$.
- Độ phức tạp thời gian (Time Complexity): $O(n \log n)$. Nó đến từ việc ta sắp xếp mảng
projectstăng dần theo thời gian kết thúc dự án, và từ trường hợp tệ nhất của hàm phải lấp đầy mảngf; mà hàmfindJgiờ có độ phức tạp thời gian là $O(\log n)$ nên độ phức tạp thời gian của hàmTry()giờ chỉ còn $O(n \log n)$. Từ đó ta có độ phức tạp thời gian là $O(2 \times n \log n)$; theo quy tắc Big O thì sẽ là $O(n \log n)$.
Với $n$ tối đa = $2 \times 10^5$ thì ta sẽ cần tầm $2 \times 2 \times 10^5 \times \log_2(2 \times 10^5)$ $\approx 7 \times 10^6$ phép tính. Vậy với cách làm trên là ta đã có thể AC (Accepted – được chấp nhận) bài này rồi.
Try(n) gọi Try(n - 1), Try(n - 2), … nên độ sâu đệ quy có thể lên tới $2 \times 10^5$ tầng. Trên Codeforces bộ nhớ stack rất rộng nên code này AC bình thường. Nhưng trên máy cá nhân hoặc hệ thống chấm có stack nhỏ (ví dụ stack mặc định của Windows chỉ 1 MB, Linux thường 8 MB) thì chương trình có thể bị tràn stack và báo Runtime Error: mình chạy thử với stack 8 MB và test $n = 2 \times 10^5$ thì code này bị lỗi. Nếu gặp tình huống đó thì các bạn dùng cách quy hoạch động bottom-up ở phần đọc thêm dưới đây, không dùng đệ quy nên không bao giờ bị lỗi này.ACĐọc thêm: quy hoạch động bottom-up
Ta đã có cách quy hoạch động top-down rồi thì ta cũng sẽ có cách quy hoạch động bottom-up. Chính là anh em sẽ tạo ra công thức truy hồi đó. Cho anh em nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau:
Bước 1: Xác định bài toán con. Gọi F[i] là số tiền tối đa ta có thể kiếm được từ $i$ dự án đầu tiên (các dự án đã được sắp xếp tăng dần theo thời gian kết thúc).
Bước 2: Xác định bài toán cơ sở. Ở phần này thì anh em sẽ thấy nó na ná phần điều kiện dừng đó. Ta có các trường hợp sau:
- Khi ta không làm dự án nào ($i = 0$): tại trường hợp này thì đương nhiên ta không kiếm được đồng nào rồi. Vậy
F[0] = 0. - Khi ta chỉ xét dự án đầu tiên ($i = 1$): trường hợp này số tiền nhiều nhất ta kiếm được chính là tiền từ dự án đầu tiên, vì ta chỉ đang xét 1 dự án đầu tiên thôi mà. Vậy
F[1] = projects[1].p.
Bước 3: Xác định đáp án của bài toán. Hiển nhiên sẽ là F[n] rồi; vì F[n] chính là số tiền nhiều nhất ta có thể kiếm được từ $n$ dự án đầu tiên mà.
Bước 4: Xác định công thức truy hồi. Ở đây nó cũng tương tự như phần xử lý chạy ở cách đệ quy nha; giờ giả sử ta đang xét $i$ dự án đầu tiên, ta có 2 trường hợp là:
- Ta không làm dự án thứ $i$: vậy số tiền nhiều nhất ta có thể kiếm được từ $i$ dự án đầu tiên mà không làm dự án thứ $i$ sẽ = số tiền nhiều nhất ta có thể kiếm được từ $i - 1$ dự án đầu tiên. Viết lại ta sẽ có:
F[i]tại trường hợp không làm dự án thứ $i$ =F[i - 1]. - Ta có làm dự án thứ $i$: vậy số tiền nhiều nhất ta có thể kiếm được sẽ = số tiền kiếm được từ dự án thứ $i$ + số tiền tối đa có thể kiếm được từ $j$ dự án đầu tiên (với $j < i$, $j$ lớn nhất có thể, thời gian kết thúc dự án $j$ < thời gian bắt đầu dự án $i$). Vì ta làm dự án $i$ thì dĩ nhiên ta sẽ nhận được số tiền từ dự án $i$ rồi. Các dự án được sắp xếp tăng dần theo thời gian kết thúc, từ đó ta cần tìm dự án có số thứ tự lớn nhất mà có thời gian kết thúc không bị đè vào thời gian bắt đầu dự án $i$ (nếu đè vào thì làm sao mà ta làm được dự án $i$ phải không). Ta cần số thứ tự lớn nhất, bởi ta thấy làm càng nhiều dự án, ta càng có thể kiếm được nhiều tiền. Để tìm được $j$ thì ta có thể làm một vòng for từ $i - 1$ về tới 1, điều này có độ phức tạp là $O(n)$. Vậy ta phải tối ưu bằng cách dùng hàm
findJmà ta đã cải tiến nhờ sử dụng tìm kiếm nhị phân (chính là cách bên trên đó), tìm được $j$ từ $i$ với độ phức tạp là $O(\log n)$. Từ đó:F[i]tại trường hợp có làm dự án $i$ =projects[i].p + F[findJ(i)].
Từ 2 trường hợp trên, ta thấy số tiền tối đa ta có thể kiếm được từ $i$ dự án đầu tiên = max(trường hợp 1 (không làm dự án $i$), trường hợp 2 (có làm dự án $i$)). Vậy công thức truy hồi sẽ là:
Chạy thử công thức với ví dụ của đề (các dự án đã sắp xếp như bảng ở trên; ô xanh là lựa chọn tốt hơn):
| i | Dự án i | findJ(i) | Không làm i | Có làm i | F[i] |
|---|---|---|---|---|---|
| 0 | không có dự án nào ⇒ F[0] = 0 | 0 | |||
| 1 | [2, 4], p = 4 | chỉ có 1 dự án ⇒ F[1] = p[1] | 4 | ||
| 2 | [3, 6], p = 6 | 0 | F[1] = 4 | 6 + F[0] = 6 | 6 |
| 3 | [5, 7], p = 3 | 1 | F[2] = 6 | 3 + F[1] = 7 | 7 |
| 4 | [6, 8], p = 2 | 1 | F[3] = 7 | 2 + F[1] = 6 | 7 |
Đáp án F[4] = 7, đúng với kết quả đề cho. Sau đây là Source Code của mình về ý tưởng trên cho bạn nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
struct Data {
int a, b;
ll p;
};
bool comp(const Data &a, const Data &b) {
return a.b < b.b;
}
const int N = 2 * (int)1e5 + 5;
Data projects[N];
ll f[N];
int findJ(int i) {
Data x;
x.b = projects[i].a;
return (lower_bound(projects + 1, projects + i, x, comp) - projects) - 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> projects[i].a >> projects[i].b >> projects[i].p;
}
sort(projects + 1, projects + n + 1, comp);
f[0] = 0;
f[1] = projects[1].p;
for(int i = 2; i <= n; ++i) {
f[i] = max(f[i - 1], f[findJ(i)] + projects[i].p);
}
cout << f[n];
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
projects = []
for i in range(n):
a, b, p = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
projects.append((b, a, p))
projects.sort() # sắp xếp tăng dần theo thời gian kết thúc
ends = [0] + [b for b, a, p in projects] # ends[i] = thời gian kết thúc dự án i (lưu từ 1)
f = [0] * (n + 1)
for i in range(1, n + 1):
b, a, p = projects[i - 1]
j = bisect_left(ends, a, 1, i) - 1 # j lớn nhất (j < i) có ends[j] < a
f[i] = max(f[i - 1], f[j] + p)
print(f[n])
main()Bản Python là mình viết thêm cho bạn nào code Python, cùng ý tưởng y như C++: hàm bisect_left đóng vai trò giống lower_bound, và đọc toàn bộ input một lần cho nhanh.
Đánh giá độ phức tạp của cách làm trên:
- Độ phức tạp không gian (Space Complexity): $O(N)$.
- Độ phức tạp thời gian (Time Complexity): $O(n \log n)$. Độ phức tạp thời gian của cách này vẫn giống cách quy hoạch động top-down mà thôi. Tuy nhiên trong thực tế cách này của ta sẽ chạy nhanh hơn và ăn ít bộ nhớ hơn một chút so với cách quy hoạch động top-down vì không phải tốn cho việc gọi đệ quy nữa. Với cách này ta cũng đã AC được bài này rồi. Ở cách này với $n = 2 \times 10^5$ thì ta cũng chỉ tốn tầm xấp xỉ $7 \times 10^6$ phép tính mà thôi.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét