Qua cầu
Đề bài
Có $n$ người cần qua bên kia cầu trong đêm. Vì cầu yếu nên chỉ đi một lúc tối đa được hai người. Trong đêm tối họ phải dùng đèn nhưng cả nhóm chỉ có 1 cái đèn. Vì vậy mỗi lần hai người cầm đèn qua sông thì phải có một người cầm đèn quay trở lại. Mỗi người qua cầu với các tốc độ lần lượt là: $a_1, a_2, a_3, \ldots, a_n$ giây. Hai người đi cùng nhau thì sẽ đi theo vận tốc của người đi chậm hơn. Hỏi để tất cả $n$ người đều qua sông được thì phải tốn ít nhất là bao nhiêu giây?
Dữ liệu nhập
- Dòng đầu tiên là số nguyên $n$ ($1 \le n \le 10^6$).
- Dòng thứ 2 gồm $n$ số nguyên $a_1, a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 100$), mỗi số cách nhau một khoảng trắng.
Dữ liệu xuất: là thời gian ít nhất để $n$ người đi qua cầu.
Subtask
- 30% số test đầu tiên có $n \le 20$.
- 30% số test tiếp theo có $n \le 10^3$.
- 40% số test còn lại có $n \le 10^6$.
4
1 3 8 12225
1 3 6 8 12291
44Trong test 1 đi theo cách như sau (ô cam là người vừa di chuyển):
| Bước | Đầu cầu | Hành động | Bên kia cầu | Thời gian | Cộng dồn |
|---|---|---|---|---|---|
| 1 | 34 | Người 1 và 2 qua cầu → 🔦 | 12 | +3 | 3 |
| 2 | 134 | Người 1 cầm đèn quay trở lại ← 🔦 | 2 | +1 | 4 |
| 3 | 1 | Người 3 và 4 qua cầu → 🔦 | 234 | +12 | 16 |
| 4 | 12 | Người 2 cầm đèn quay trở lại ← 🔦 | 34 | +3 | 19 |
| 5 | (trống) | Người 1 và 2 qua cầu → 🔦 | 1234 | +3 | 22 |
Lờ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 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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: có $n$ ($1 \le n \le 10^6$) người cần qua cầu trong đêm tối. Cầu rất yếu nên chỉ đi 1 lúc tối đa được 2 người. Họ cần có đèn mới qua được cầu, mà cả nhóm chỉ có duy nhất 1 cái đèn. Vì vậy nên mỗi lần 2 người qua sông thì phải cử 1 người cầm đèn quay trở lại. Mỗi người qua cầu với các tốc độ lần lượt là a[i] giây ($1 \le a[i] \le 100$). Hai người đi cùng nhau thì sẽ đi theo tốc độ của người đi chậm hơn. Ta cần tìm thời gian ít nhất để tất cả $n$ người qua bên kia cầu.
Test 1 thì đề đã giải thích ở trên rồi. Với test 2 ($N = 5$; a = {1, 3, 6, 8, 12}) thì đi theo cách như sau:
| Bước | Đầu cầu | Hành động | Bên kia cầu | Thời gian | Cộng dồn |
|---|---|---|---|---|---|
| 1 | 345 | Người 1 và 2 qua cầu → 🔦 | 12 | +3 | 3 |
| 2 | 1345 | Người 1 cầm đèn quay trở lại ← 🔦 | 2 | +1 | 4 |
| 3 | 13 | Người 4 và 5 qua cầu → 🔦 | 245 | +12 | 16 |
| 4 | 123 | Người 2 cầm đèn quay trở lại ← 🔦 | 45 | +3 | 19 |
| 5 | 2 | Người 1 và 3 qua cầu → 🔦 | 1345 | +6 | 25 |
| 6 | 12 | Người 1 cầm đèn quay trở lại ← 🔦 | 345 | +1 | 26 |
| 7 | (trống) | Người 1 và 2 qua cầu → 🔦 | 12345 | +3 | 29 |
Còn test 3 ($N = 1$; a = {4}): người 1 qua cầu mất 4 giây. Tổng cộng mất 4 giây.
Nhận ra tư tưởng tham lam
Cách làm đơn giản nhất của bài này chính là vét cạn, chính là ta thử mọi trường hợp có thể đó. Đến đây thì các bạn sẽ nghĩ tới việc ta tạo ra 2 mảng: một mảng là số người ở đầu cầu, còn lại là số người ở cuối cầu. Mỗi bước ta sẽ chọn ra 2 người bất kì trong đầu cầu để đi qua bên kia cầu, rồi sau đó lại chọn ra 1 người bất kì ở chân cầu để cầm đèn quay trở lại. Để thực hiện ý tưởng đó thì code của ta sẽ khá là phức tạp, và chắc chắn ta không thể nào AC (Accepted – được chấp nhận) ở bài này được. Ta sẽ cần một cách vét cạn mà nó tối ưu hơn, dễ code và dễ cải tiến hơn.
Thì đọc vào yêu cầu đề bài là dễ dàng nhìn ra được tư tưởng để giải quyết bài này. Bài này ta cần phải dùng kỹ thuật tham lam (Greedy) để giải quyết. Kể cả bạn nào có không biết về kỹ thuật tham lam này thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết. Cho bạn nào không biết thì mình có thể nói nhanh như thế này: tham lam ở đây nghĩa là ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách giải quyết tốt nhất đó; nếu lại đứng trước nhiều lựa chọn cách giải quyết khác nhau nữa thì ta lại cố gắng chọn theo cách giải quyết tốt nhất trong số đó; tóm lại cứ tốt nhất mà triển, vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ còn lại không có công thức từng bước cụ thể giải quyết như mấy thuật toán khác. Mà ta có thể giải quyết theo cách bất kỳ, miễn cái tư tưởng mà ta giải quyết luôn là chọn theo hướng tốt nhất trong các lựa chọn thì đó chính là tư tưởng của tham lam. Thì tại sao bài này lại có thể nhìn ra tư tưởng của nó là tham lam? Đọc đề bài là thấy rõ mùi rồi hehe, muốn xử lý theo quy luật gì gì đó để sau cùng đáp án phải là nhỏ nhất/lớn nhất các kiểu, đọc kiểu này phát thấy mùi tham lam ngay 🤪. Cụ thể ở bài này là ta muốn tìm thời gian ít nhất để $n$ người qua cầu đó.
Giờ ta nhìn vào 2 cái giải thích của test 1 và test 2. Ta sẽ thấy rằng cần có một số người đi qua, đi lại trên cây cầu nhiều lần để đưa đèn cho những người khác, nên ta sẽ chọn người nào đi nhanh nhất để tiết kiệm thời gian. Chính vì vậy nên ta sẽ sắp xếp mảng a tăng dần. Từ đó những người đi nhanh nhất sẽ ở đầu của mảng a.
Ta cũng thấy ở test case mẫu số 1 và 2, mảng a ở đầu vào đã được sắp xếp tăng dần; ta dễ dàng nhìn ra những người cầm đèn quay trở lại chỉ có thể là người số 1 (người đi nhanh nhất) hoặc người số 2 (người đi nhanh nhì).
Còn trường hợp qua bên kia cầu: trừ những trường hợp đầu tiên (2 người nhanh nhất qua bên kia cầu), thì ta sẽ chọn 2 người chậm nhất (người chậm nhất và chậm nhì ở đầu cầu) để cùng nhau đi qua cầu (ở test case 1 là người 3 và người 4; ở test case 2 là người 4 và người 5), vì khi đó thì người chậm thứ nhì sẽ không bị tính thời gian (vì tính thời gian là người chậm nhất mà). Hoặc là ta sẽ chọn người chậm nhất đi cùng với người nhanh nhất để qua bên kia cầu (ở test case 2 là người số 1 đi với người số 3; lúc này đầu cầu chỉ còn 3 người là người số 1, 2 và 3. Nên người nhanh nhất là người số 1, người chậm nhất là người số 3).
Tiếp tới ta sẽ thấy, những người cuối cùng ở đầu cầu sẽ là những người nhanh nhất (tại họ phải cầm đèn về, hoặc nhường cho những người chậm nhất đi trước, hoặc 1 người nhanh nhất đi cùng 1 người chậm nhất). Ở test case 1 ta thấy lúc cuối đầu cầu còn 2 người là người số 1 và 2; ở test case 2 cũng vậy.
Em nhập thời gian qua cầu của từng người rồi bấm Tiếp để xem cả nhóm qua cầu theo tư tưởng tham lam: mỗi lần chỉ lo đưa 2 người chậm nhất qua, bằng cách rẻ hơn trong 2 cách (ô cam là người vừa di chuyển):
TLECách 1: vét cạn bằng đệ quy
Để làm được theo ý tưởng trên, ta sẽ xây dựng hàm đệ quy như sau. Trước hết hãy nhớ sort mảng a tăng dần.
Gọi hàm Try(n) sẽ trả về thời gian ngắn nhất để tất cả $n$ người đầu tiên ở đầu cầu qua sông (qua bên kia cầu).
Điều kiện dừng: như đã phân tích ở trên, tư tưởng tham lam của ta là chỉ quan tâm đến thằng nhanh nhất, nhanh nhì; chậm nhất, chậm nhì mà thôi. Mà để có 4 thành phần đó thì ít nhất ở đầu cầu phải có 4 người. Từ đó điều kiện dừng của ta là khi ở đầu cầu có ít hơn 4 người ($n \le 3$). Cụ thể sẽ là như sau:
- $n = 1$: chỉ có 1 người đầu tiên ở đầu cầu. Vậy ta sẽ tốn mất thời gian là
a[1]để qua sông, vì người đó đi một mình qua cầu là được:if(n == 1) return a[1]; - $n = 2$: có 2 người đầu tiên ở đầu cầu. Vậy ta sẽ tốn mất thời gian là
a[2]để qua sông, vì người thứ 2 và người thứ nhất cùng nhau đi qua sông thì sẽ đi với tốc độ của người chậm hơn (người số 2) nên sẽ tốna[2]giây:if(n == 2) return a[2]; - $n = 3$: có 3 người đầu tiên ở đầu cầu. Đoạn này thì anh em lôi nháp ra. Ta có $a[1] \le a[2] \le a[3]$; đâu sẽ là cách qua tối ưu nhất ta tạo ra được? Cách qua tối ưu nhất ta có chính là giống bước 5 ở test case 2 cho đến bước cuối: ta sẽ cho người 1 với người 3 qua cầu cùng nhau, tốn
a[3]giây; sau đó người 1 cầm đèn quay lại, tốna[1]giây. Rồi người 1 và người 2 cùng nhau qua cầu, tốna[2]giây. Tổng cộng ta tốna[1] + a[2] + a[3]giây:if(n == 3) return a[1] + a[2] + a[3];
Xử lý chạy: bước đến đây, ta đã chắc chắn rằng số người ở đầu cầu sẽ ≥ 4 rồi. Tức ta sẽ có người đi nhanh nhất, nhì và người chậm nhất, nhì ở đầu cầu. Giả sử ta đang xét người thứ $n$ (người chậm nhất ở đầu cầu). Sẽ có những cách nào để người này đi qua cầu mà làm cho thời gian $n$ người đầu tiên đi qua cầu được tối thiểu nhất có thể?
Coi như $n - 1$ người trước đó đã qua hết (bên kia chắc chắn có người 1). Người 1 cầm đèn về: a[1]; người 1 và người $n$ cùng qua: a[n].
Coi như $n - 2$ người trước đó đã qua hết. Người 1 cầm đèn về: a[1]; 2 người chậm nhất cùng qua: a[n]; người 2 cầm đèn về: a[2]; người 1 và 2 cùng qua: a[2].
Trường hợp 1 (người thứ $n$ đi cùng người thứ 1 – người nhanh nhất): lúc này ta chỉ có người thứ $n$ ở đầu cầu mà thôi, vì ta coi như $n - 1$ người trước đó đều đã qua hết bên kia cầu (chắc chắn bên kia cầu có người số 1). Giờ để người thứ $n$ qua được bên kia cầu thì ta sẽ cần 1 người đem đèn về, và đó sẽ là người nhanh nhất (người số 1). Việc đem đèn về sẽ tốn a[1] giây; sau đó người thứ 1 và người thứ $n$ sẽ cùng nhau đi qua cầu, ta sẽ tốn a[n] giây. Vậy thời gian ít nhất để $n$ người qua sông ở trường hợp này sẽ = (thời gian ít nhất để $n - 1$ người qua sông) + (thời gian để người thứ $n$ qua sông ở trường hợp này) = Try(n - 1) + a[1] + a[n].
Trường hợp 2 (2 người chậm nhất đi với nhau, tức người thứ $n$ đi cùng người thứ $n - 1$ – người chậm nhì): lúc này ta chỉ có 2 người là người thứ $n$ và người thứ $n - 1$ ở đầu cầu mà thôi, vì ta coi như $n - 2$ người trước đó đều đã qua hết bên kia cầu (chắc chắn bên kia cầu có người số 1 và người số 2, chính là 2 người nhanh nhất đó). Giờ để 2 người chậm nhất này qua được bên kia cầu, ta sẽ cho người thứ 1 đem đèn về, việc này tốn a[1] giây. Sau đó ta cho 2 người chậm nhất cùng nhau qua cầu, việc này tốn a[n] giây (việc này giúp ta bỏ đi được thời gian qua cầu của người thứ $n - 1$). Bây giờ ở bên đầu cầu chỉ còn người thứ 1 và đang không có đèn. Giờ ta cử người thứ 2 (người nhanh thứ nhì mà đang ở bên kia cầu) đi cầm đèn về, tốn a[2] giây. Sau đó người thứ 2 và người thứ nhất cùng nhau qua cầu, tốn tiếp a[2] giây. Tổng cộng: Try(n - 2) + a[1] + a[n] + 2 * a[2].
Từ 2 trường hợp trên, ta thấy thời gian ít nhất để $n$ người qua sông sẽ = min(trường hợp 1, trường hợp 2). Vậy ta sẽ kết luận rằng với $n > 3$ (vượt qua điều kiện dừng) thì:
Sau đây là Source Code của mình về ý tưởng trên cho anh em 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;
const int nMax = 1e6 + 5;
int a[nMax];
int Try(int n){
if(n == 1){
return a[1];
}
if(n == 2){
return a[2];
}
if(n == 3){
return a[1] + a[2] + a[3];
}
return min(Try(n - 1) + a[1] + a[n], Try(n - 2) + a[1] + a[n] + 2 * a[2]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
cout << Try(n);
return 0;
}Giải thích một số chỗ trong code ở trên:
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main 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 $10^6$ số, nên các bạn nên thêm 2 dòng này 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é.sort(a + 1, a + n + 1);Đây chính là mình sort mảng tăng dần từ phần tử số 1 tới phần tử thứ $n$.Try(n);Ta cần tìm thời gian nhỏ nhất để $n$ người đầu tiên qua sông nên ta gọi hàmTry(n). Mảngata đã khai báo làm biến toàn cục để có thể dễ dàng truy cập trong hàmTry().
Try(n) lại tách ra 2 nhánh Try(n - 1) và Try(n - 2), số lần gọi tăng theo cấp số mũ. Tuy nhiên hãy vẫn nên cài đặt nó để sau này ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu, hoặc biết đâu ta có thể cải tiến nó thành quy hoạch động top-down. Bạn nào chưa biết cách lấy nó làm công cụ kiểm tra tính chính xác thì có thể xem qua bài viết này của mình nha: Hạn chế lỗi Wrong Answer bằng vét cạn.ACCách 2: đệ quy có nhớ (quy hoạch động top-down)
Bạn nào mà có ý tưởng mà code vét cạn làm được đến đây là đã làm xong hơn 90% cách để có thể AC bài này rồi đó. Ta dễ dàng nhìn ra ta có thể cải tiến bài này lên quy hoạch động top-down – đệ quy có nhớ vô cùng dễ dàng.
Nếu ta đã từng tính Try(4) rồi, khi ta gặp lại Try(4), ta lại đi tính lại đúng không? Tổng quát là nếu ta đã từng tính Try(n) rồi, việc gặp lại Try(n) thì lại đi tính lại nó; điều đó làm cách code vét cạn trở nên rất lâu. Ta sẽ cải tiến lên thành đệ quy "có nhớ" bằng cách dùng 1 kiểu dữ liệu để lưu trữ kết quả của hàm Try(n).
Ta thấy hàm Try(n) chỉ có biến $n$ bị thay đổi khi ta gọi đệ quy. Nên ta sẽ dùng mảng một chiều F[nMax] (nMax là giá trị tối đa của $n$, sẽ = $10^6$ và mình cộng dư thêm 5). Từ đó phần tử F[n] sẽ lưu kết quả của hàm Try(n). Ta khai báo mảng F là mảng toàn cục nên tất cả các phần tử trong mảng sẽ được gán mặc định bằng 0. Hàm Try(n) cũng không thể nào trả về giá trị 0 được vì thời gian nhỏ nhất có thể trả về cũng sẽ chỉ = 1 mà thôi. Nên từ đó ta không cần phải lấp đầy mảng F nữa. Tự động ta đã có: nếu F[n] != 0 tức là ta đã tính Try(n) rồi và đã lưu kết quả vào F[n]. Vậy sau mục điều kiện dừng, ta check nếu F[n] != 0 thì ta sẽ return về F[n] luôn. Còn ngược lại, tức F[n] = 0, tức ta chưa tính Try(n), thì ta sẽ đi tính rồi lưu kết quả vào F[n]. Sau đó trả về F[n] là được rồi.
Sau đây là Source Code của mình về ý tưởng trên cho anh em 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;
const int nMax = 1e6 + 5;
int a[nMax], f[nMax];
int Try(int n){
if(n == 1){
return a[1];
}
if(n == 2){
return a[2];
}
if(n == 3){
return a[1] + a[2] + a[3];
}
if(f[n]){
return f[n];
}
return f[n] = min(Try(n - 1) + a[1] + a[n], Try(n - 2) + a[1] + a[n] + 2 * a[2]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
cout << Try(n);
return 0;
}Đá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 dùng mảng
avà mảngf; nhưng theo quy tắc nhân Big O nên sẽ thành $O(n)$. - Độ phức tạp thời gian (Time Complexity): $O(n \log n)$. Thực chất chính là $O(n \log n + 2 \times n)$: độ phức tạp của bước sort mảng
alà $O(n \log n)$; $O(n)$ của việc đọc vào và $O(n)$ của hàmTry(n), vì trong trường hợp tệ nhất ta phải lấp đầy mảngF, mà mảngFcó tối đa $n$ phần tử nên hàmTry(n)chỉ có độ phức tạp thời gian là $O(n)$ mà thôi. Theo quy tắc cộng Big O thì nó sẽ là $O(n \log n)$.
Với cách trên thì ta đã hoàn toàn có thể AC bài này rồi 😁.
Try(n) gọi Try(n - 1), Try(n - 2), … nên với $n = 10^6$ thì độ sâu đệ quy lên tới khoảng 1 triệu 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ỏ (stack mặc định của Windows chỉ 1 MB, Linux thường 8 MB) thì chương trình sẽ bị tràn stack và báo Runtime Error: mình chạy thử với stack 8 MB và test $n = 10^6$ thì code này bị lỗi ngay. 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 ngay 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 đó. Ở bài này quan trọng nhất là việc ta nghĩ ra được ý tưởng và nhìn ra tư tưởng tham lam thôi. Còn công thức truy hồi quy hoạch động thì ta sẽ thấy nó giống hệt cách vét cạn thôi. Chỉ cần có ý tưởng thì việc ta làm y như phần vét cạn vậy. 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à thời gian tối thiểu để $i$ người đầu tiên đi qua sông.
Bước 2: Xác định trường hợp cơ sở. Như ở điều kiện dừng phần vét cạn ta có: F[1] = a[1]; F[2] = a[2]; F[3] = a[1] + a[2] + a[3].
Bước 3: Xác định đáp án của bài toán. Hiển nhiên sẽ là F[n] rồi, chính là thời gian tối thiểu để $n$ người qua sông.
Bước 4: Xác định công thức truy hồi. Ở phần vét cạn ta có Try(n) = min(Try(n - 1) + a[1] + a[n], Try(n - 2) + a[1] + a[n] + 2 * a[2]), vậy ở công thức truy hồi ta sẽ chuyển thành:
Còn giờ mình sẽ đi chứng minh công thức truy hồi nếu anh em không muốn biến từ phần xử lý chạy ở vét cạn qua. Ta có 2 trường hợp sau:
- Người thứ $i$ đi chung với người đi nhanh nhất (người thứ nhất): lúc này người thứ nhất cần phải quay lại cầu (vì $i - 1$ người trước đó đang ở bên kia cầu) với thời gian
a[1], sau đó 2 người đi qua cầu với thời giana[i]. Công thứcF[i] = F[i - 1] + a[1] + a[i](F[i - 1]chính là thời gian ngắn nhất để $i - 1$ người trước đó qua cầu; sau đó ta cộng với thời gian người thứ 1 cầm đèn qua + thời gian người thứ 1 và người thứ $i$ qua cầu). - Người thứ $i$ đi chung với người thứ $i - 1$: lúc này ta cần một người cầm đèn đi về lại cho 2 người này qua, ta sẽ cho người thứ 1 đi; sau khi người thứ $i$ và $i - 1$ qua cầu thì cần phải cho người thứ 2 quay về đón người thứ 1 (thời gian đi và về đều là
a[2]). Ta có:F[i] = F[i - 2] + a[1] + a[i] + 2 * a[2](F[i - 2]chính là thời gian ngắn nhất để $i - 2$ người trước đó qua cầu; sau đó ta cộng với thời gian người thứ 1 cầm đèn qua + thời gian người thứ $i$ và người thứ $i - 1$ qua cầu + thời gian người 2 cầm đèn qua đón người 1, rồi sau đó cùng người 1 đi qua cầu).
Vậy tổng quát lại ta có F[i] = min(trường hợp 1, trường hợp 2). Và để áp dụng công thức trên ta làm 1 vòng for($i$) chạy tăng dần thôi; $i$ sẽ chạy từ 4 và chạy tới $n$. Chạy thử với test 2 (a = {1, 3, 6, 8, 12}, ô xanh là lựa chọn tốt hơn):
| i | a[i] | Người i đi cùng người 1 | Người i đi cùng người i − 1 | F[i] |
|---|---|---|---|---|
| 1 | 1 | F[1] = a[1] | 1 | |
| 2 | 3 | F[2] = a[2] | 3 | |
| 3 | 6 | F[3] = a[1] + a[2] + a[3] = 1 + 3 + 6 | 10 | |
| 4 | 8 | F[3] + a[1] + a[4] = 10 + 1 + 8 = 19 | F[2] + a[1] + a[4] + 2·a[2] = 3 + 1 + 8 + 6 = 18 | 18 |
| 5 | 12 | F[4] + a[1] + a[5] = 18 + 1 + 12 = 31 | F[3] + a[1] + a[5] + 2·a[2] = 10 + 1 + 12 + 6 = 29 | 29 |
Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int nMax = 1e6 + 5;
int a[nMax], f[nMax];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
if(n < 3){
cout << a[n];
return 0;
}
f[1] = a[1];
f[2] = a[2];
f[3] = a[1] + a[2] + a[3];
for(int i = 4; i <= n; ++i){
f[i] = min(f[i - 1] + a[1] + a[i], f[i - 2] + a[1] + a[i] + 2 * a[2]);
}
cout << f[n];
return 0;
}n = int(input())
a = [0] + list(map(int, input().split()))
a[1:n+1] = sorted(a[1:n+1])
if n < 3:
print(a[n])
else:
f = [0] * (n + 5)
f[1] = a[1]
f[2] = a[2]
f[3] = a[1] + a[2] + a[3]
for i in range(4, n + 1):
f[i] = min(f[i - 1] + a[1] + a[i], f[i - 2] + a[1] + a[i] + 2 * a[2])
print(f[n])Đánh giá độ phức tạp của cách làm trên: với cách trên ta sẽ có độ phức tạp không gian và thời gian giống như cách quy hoạch động top-down. Nhưng khác biệt ở chỗ về mặt thực tế, code ta sẽ chạy nhanh và ăn ít bộ nhớ hơn (nếu test case lớn ta sẽ thấy rõ), bởi vì ta không phải tốn thời gian và bộ nhớ cho việc gọi đệ quy nữa.
ACTham khảo: cách thuần tham lam, không cần quy hoạch động
Ta có cả cách làm bài này theo 1 cách khác mà không cần dùng quy hoạch động hay đệ quy cơ, bởi vì tham lam chỉ là dạng tư tưởng thôi, còn lại để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác nữa (ở trên là ta dùng đệ quy hoặc ta dùng quy hoạch động). Ở phần này mình sẽ làm theo cách thuần tham lam luôn, tức chỉ dùng vòng lặp thôi (có sort mảng nha). Mình sẽ không có dùng đệ quy hay là quy hoạch động.
Để thực hiện cách tham lam này ta sẽ coi như (đang là giả sử thôi nha) 2 đứa nhanh nhất (người thứ 1 và người thứ 2) đã ở bên kia cầu. Giờ ta cần đưa 2 người chậm nhất qua bên kia cầu (người thứ $n$ và người thứ $n - 1$). Vậy giờ ta sẽ có 2 cách để đưa 2 người chậm nhất này qua cầu:
- Cách đầu: cho người chạy nhanh nhất ở bên kia cầm đèn chạy về; sau đó đi cùng người chậm nhất qua bên kia; xong lại chạy về để đón người chậm nhì qua bên kia. Ta sẽ tốn thời gian là:
cnt1 = a[1] + a[n] + a[1] + a[n - 1]. - Cách thứ 2: giống với trường hợp 2 ở quy hoạch động. Chính là ta sẽ cho người thứ nhất cầm đèn chạy về; sau đó cho 2 người chậm nhất đi cùng nhau qua bên kia cầu; rồi cho người thứ 2 cầm đèn chạy về để đón người thứ nhất. Vậy ta sẽ tốn thời gian là:
cnt2 = a[1] + a[n] + 2 * a[2].
Vậy theo tư tưởng tham lam, ta sẽ lấy thời gian ngắn nhất trong 2 trường hợp trên để đưa 2 người chậm nhất qua bên kia. Từ đó ta cộng thời gian ngắn nhất vào biến kết quả (mình tạo là res: thời gian ít nhất để đưa tất cả mọi người qua bên kia cầu). Rồi $n$ sẽ trừ đi 2, tại vì ta vừa đưa xong 2 người chậm nhất qua bên kia mà. Ta sẽ lặp cho đến khi $n \le 3$ thì thôi. Khi mà $n \le 3$ rồi thì ta sẽ quay lại với 3 điều kiện dừng mà ta đã tạo ra. Từ đó ứng với mỗi $n$ thì ta sẽ cộng thêm vào biến kết quả một trường hợp.
Sau đây là Source Code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
Xem code cách thuần tham lam
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int a[1000005];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
int res = 0;
while(n > 3){
int cnt1 = a[1] + a[n] + a[1] + a[n - 1];
int cnt2 = a[1] + a[n] + 2 * a[2];
res += min(cnt1, cnt2);
n -= 2;
}
if(n == 3){
res += a[1] + a[2] + a[3];
}
else if(n == 2){
res += a[2];
}
else{
res += a[1];
}
cout << res;
return 0;
}n = int(input())
a = [0] + list(map(int, input().split()))
a[1:n+1] = sorted(a[1:n+1])
res = 0
while n > 3:
cnt1 = a[1] + a[n] + a[1] + a[n - 1]
cnt2 = a[1] + a[n] + 2 * a[2]
res += min(cnt1, cnt2)
n -= 2
if n == 3:
res += a[1] + a[2] + a[3]
elif n == 2:
res += a[2]
else:
res += a[1]
print(res)Với cách trên thì độ phức tạp không gian của ta đúng là chỉ còn $O(n)$ vì ta chỉ còn dùng một mảng a mà thôi. Còn độ phức tạp thời gian của ta vẫn là $O(n \log n)$; nhưng để mà so sánh vòng lặp for($i$) ở cách quy hoạch động bottom-up với vòng lặp while ở đây thì vòng lặp ở đây sẽ nhanh hơn vì ta thấy n -= 2, tức giảm đi 2. Vậy nhìn chung cách này sẽ còn chạy nhanh và ăn ít bộ nhớ hơn nữa.
Lúc viết bài mình có nói cách thuần tham lam này không đảm bảo tính chính xác 100% (như cái cách mà anh em dùng tham lam trong bài đổi tiền đó), và mình đã xây dựng cả tool test để so sánh kết quả code trên với cách quy hoạch động bottom-up: mình thử mọi trường hợp với ($n = 3$; $n = 4$; $n = 5$ và $1 \le a[i] \le 100$) mà có thể tạo ra, và đã chạy test random $n$ và random mảng a trong 1 tiếng mà cũng không tìm ra test case khiến code trên sai nha. Code trên nộp vẫn AC bài này.
Nhận xét
Đăng nhận xét