Work

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Dễ Quy hoạch động QHĐ tuyến tính

Đề bài

Trong một dây chuyền làm việc của công ty có $N$ công nhân làm $N$ việc. Người ta đánh số cho công nhân từ 1 đến $N$ theo thứ tự đứng trong dây chuyền. Thời gian hoàn thành một công việc của người thứ $i$ là $t_i$ phút. Mỗi người cần làm xong công việc của mình nhưng được quyền làm tối đa 2 việc, vì thế họ có thể phối hợp với người đứng ngay trước mình cùng làm: nếu người thứ $i$ và người thứ $i+1$ phối hợp thì thời gian làm xong việc cho 2 người là $p_i$. Tìm phương án sao cho $N$ công việc đều hoàn thành với thời gian ít nhất.

Dữ liệu: vào từ file văn bản WORK.INP:

• Dòng thứ nhất ghi số $N$ $(1 < N \le 10^6)$.
• Dòng thứ 2 ghi thời gian làm xong việc của từng công nhân tương ứng trong dây chuyền $t_1, t_2, \ldots, t_N$ $(1 \le t_i \le 60)$.
• Dòng thứ ba ghi $N - 1$ số là thời gian cùng làm tương ứng cho các cặp công nhân nếu phối hợp $p_1, p_2, \ldots, p_{N-1}$ $(1 \le p_i \le 100)$.

Kết quả: ghi ra file WORK.OUT một số duy nhất là tổng thời gian hoàn thành công việc ít nhất của $N$ công nhân.

Ví dụ – input

5
2 5 7 8 4
3 9 10 10

Ví dụ – output

17

Giải thích ví dụ: cho người 1 và 2 phối hợp (mất $p_1 = 3$), người 3 và 4 phối hợp (mất $p_3 = 10$), người 5 làm một mình (mất $t_5 = 4$). Tổng thời gian $3 + 10 + 4 = 17$ – không có cách chia nào nhanh hơn. Nếu ai cũng làm một mình thì mất tới $2 + 5 + 7 + 8 + 4 = 26$.

Lưu ý về đọc / ghi file

Đề ghi tên file WORK.INP / WORK.OUT. Code bên dưới dùng mẹo if(fopen("WORK.INP", "r")): có file thì đọc ghi file, không có thì đọc bàn phím và in ra màn hình – nộp kiểu nào cũng chạy.

Lời mở đầu

Đây là một bài quy hoạch động "một chiều" rất đẹp để mở đầu chương: mỗi người chỉ có 2 lựa chọn – làm một mình hoặc bắt cặp với người ngay trước. Mình sẽ đi đúng lộ trình kinh điển của QHĐ: đệ quy thử hết → đệ quy có nhớ → QHĐ bảng (khử đệ quy) → tối ưu bộ nhớ chỉ còn 3 biến, và xem mỗi cách được bao nhiêu điểm trên bộ test thật.

Link nộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test4 mức NÝ tưởngf[i]Cách 1Đệ quy 4/20Cách 2Có nhớ 15/20Cách 3Bảng 20/20Cách 43 biến 20/20

Bộ testBộ test chính thức có gì?

Test	$N$	$t_i$ lớn nhất	$p_i$ lớn nhất	Đáp án lớn nhất
1–4	2 – 15	10	15	41
5–10	119 – 1.991	40	60	20.190
11–15	63.258 – 90.571	50	80	1.186.786
16–20	708.216 – 1.000.000	60	100	16.050.218

Đề không ghi subtask nhưng $N$ tăng dần theo 4 mức rõ rệt, mình tự chia như bảng dưới. Mọi giá trị đều đúng giới hạn đề ($t_i \le 60$, $p_i \le 100$). Đáp án lớn nhất khoảng $1{,}6 \cdot 10^7$ nên kiểu int là đủ. Có test $N = 2$ (đề ghi $1 < N$ nên vẫn hợp lệ). Mức 4 có tới $2 \cdot 10^6$ số trong input nên nhớ tăng tốc nhập xuất.

Mức	Điều kiện	Test	Cách 1 đệ quy	Cách 2 đệ quy có nhớ	Cách 3 QHĐ bảng	Cách 4 QHĐ 3 biến
1	$N \le 15$	1–4	qua	qua	qua	qua
2	$N \le 2000$	5–10	quá thời gian	qua	qua	qua
3	$N \le 10^5$	11–15	quá thời gian	qua	qua	qua
4	$N \le 10^6$	16–20	quá thời gian	tràn ngăn xếp*	qua	qua

* Trên máy chấm của mình (ngăn xếp 8 MB). Có máy chấm cho ngăn xếp lớn hơn thì cách 2 có thể qua, nhưng không nên trông chờ vào điều đó.

Ý tưởngNgười cuối cùng làm một mình hay bắt cặp?

Gọi $f[i]$ là thời gian ít nhất để làm xong việc của $i$ người đầu tiên. Nhìn vào người thứ $i$ (người cuối cùng của nhóm), chỉ có 2 khả năng:

• Người $i$ làm một mình, mất $t_i$; $i - 1$ người trước tự lo tốt nhất mất $f[i-1]$. Tổng: $f[i-1] + t_i$.
• Người $i$ bắt cặp với người $i - 1$, cả hai mất $p_{i-1}$; $i - 2$ người trước mất $f[i-2]$. Tổng: $f[i-2] + p_{i-1}$.

Công thức QHĐ

$f[0] = 0,\quad f[1]$ $= t_1,\quad f[i]$ $= \min\big(f[i-1] + t_i,\ \ f[i-2] + p_{i-1}\big)$ với $i \ge 2$. Đáp án là $f[N]$.

Người $i$ không thể bắt cặp với người $i + 1$ ở đây? Có chứ – nhưng trường hợp đó được tính khi ta xét người $i + 1$ (lúc đó người $i+1$ là "người cuối" bắt cặp với người đứng trước). Mỗi cách chia đội đều được đếm đúng một lần.

Em nhập dữ liệu rồi bấm Tiếp để xem bảng $f$ được điền dần (ô vàng đang tính, 2 ô xanh dương là 2 ô nó phụ thuộc):

t p

Ví dụ nhanh:

Cách 1Đệ quy thử mọi cách (qua mức 1)

Viết thẳng công thức trên thành hàm đệ quy F(i):

C++▶ Chạy tay từng dòng codeCách 1: đệ quy thuần F(i) = min(F(i−1) + t[i], F(i−2) + p[i−1]).

Dữ liệu vào (stdin) – sửa thoải mái5 2 5 7 8 4 3 9 10 10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Để ý cùng một F(2), F(1) bị gọi lại nhiều lần – số lời gọi hiện ở ô biến.

Hàm đúng, nhưng rất chậm: F(i) gọi F(i-1) và F(i-2), giống hệt dãy Fibonacci – số lời gọi tăng theo cấp số nhân, khoảng $1{,}6^N$. Cùng một F(3) bị tính đi tính lại hàng trăm lần.

Không gian$O(N)$ (độ sâu đệ quy)

Thời gian$O(1{,}6^N)$

Kết quả chạy thật: C++ đúng 4/20 test (mức 1, $N \le 15$). Từ test 5 ($N = 144$, cỡ $10^{29}$ lời gọi) trở đi đều quá thời gian. Bản Python cũng 4/20, các test lớn còn bị lỗi vượt giới hạn độ sâu đệ quy.

Cách 2Đệ quy có nhớ (qua mức 1–3)

Mỗi giá trị F(i) chỉ cần tính một lần: tính xong thì cất vào mảng memo[i], lần sau gặp lại thì trả về ngay. Mảng memo khởi tạo bằng $-1$ nghĩa là "chưa tính" (thời gian luôn $\ge 0$ nên $-1$ không nhầm với kết quả thật).

C++▶ Chạy tay từng dòng codeCách 2: đệ quy có nhớ – mỗi F(i) chỉ tính một lần.

Dữ liệu vào (stdin) – sửa thoải mái5 2 5 7 8 4 3 9 10 10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(memo[i] != -1) return memo[i]; – chính dòng này biến thời gian từ hàm mũ thành tuyến tính.
2. return memo[i] = min(a, b); vừa lưu vừa trả về.

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: đúng 15/20 test, chậm nhất khoảng 0,1 giây. 5 test mức 4 ($N \approx 10^6$) bị lỗi chạy: lời gọi F(n) gọi F(n-1) gọi F(n-2)... chồng sâu tới $10^6$ tầng, vượt quá ngăn xếp 8 MB → tràn ngăn xếp (stack overflow). Đây là điểm yếu kinh điển của đệ quy có nhớ khi $N$ lớn.

Cách 3QHĐ bảng – khử đệ quy (full điểm)

Để tính f[i] chỉ cần f[i-1] và f[i-2], nên ta tính từ nhỏ đến lớn bằng một vòng for: khi tới $i$ thì 2 ô cần dùng đã có sẵn. Không còn đệ quy, không lo tràn ngăn xếp.

C++▶ Chạy tay từng dòng codeCách 3: điền bảng f từ trái sang phải.

Dữ liệu vào (stdin) – sửa thoải mái5 2 5 7 8 4 3 9 10 10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: đúng 20/20 test, chậm nhất 0,08 giây (phần lớn thời gian là đọc $2 \cdot 10^6$ số). Bản Python đúng 20/20, chậm nhất 0,66 giây.

Cách 4Tối ưu bộ nhớ: chỉ giữ 3 biến

Cách 3 đã đủ điểm, nhưng để ý công thức chỉ "nhìn lùi" đúng 2 ô. Vậy chỉ cần giữ f2 = f[i-2], f1 = f[i-1] và tính f0 = f[i], rồi "dời cửa sổ" sang phải. Mình còn đọc luôn $p_{i-1}$ ngay trong vòng lặp nên bỏ được cả mảng p. Đây là kỹ thuật tối ưu bộ nhớ rất hay dùng ở các bài QHĐ có bảng lớn.

C++▶ Chạy tay từng dòng codeCách 4: chỉ giữ f2, f1, f0 và đọc p ngay trong vòng lặp.

Dữ liệu vào (stdin) – sửa thoải mái5 2 5 7 8 4 3 9 10 10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Thứ tự trong input là: cả dòng $t$ trước, rồi mới tới dòng $p$. Vì vậy vẫn phải đọc hết mảng t trước; còn $p_1, p_2, \ldots$ thì vừa đọc vừa dùng theo đúng thứ tự $i = 2, 3, \ldots$
2. f2 = f1; f1 = f0; phải gán theo đúng thứ tự này, đảo ngược sẽ làm mất giá trị f1 cũ.

Không gian$O(N)$ cho mảng t (bảng f chỉ còn $O(1)$)

Thời gian$O(N)$

Kết quả chạy thật: đúng 20/20 test, chậm nhất 0,08 giây – thời gian như cách 3 nhưng bỏ được 2 mảng $10^6$ phần tử.

Ghi chú của mình: 20 test chia 4 mức $N \le 15$ / $2000$ / $10^5$ / $10^6$. Kết quả chạy thật (C++): đệ quy 4/20, đệ quy có nhớ 15/20 (tràn ngăn xếp ở mức 4), QHĐ bảng và QHĐ 3 biến đều 20/20 trong 0,08 giây. Python QHĐ bảng cũng 20/20 (≤ 0,66 s).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇