Trong một day 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 à 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 gồm: - Dòng thứ nhất ghi số N ( 1<N<=10^6) - Dòng thứ hai 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 t1, t2, , tn (1<t i <=60) - Dòng thứ ba ghi N -1 số thời gian cùng làm tương ứng cho số cặp công nhân nếu phối hợp p1, p2, ,pn-1 (1<p N <=100) Kết quả: ghi ra file WORK.OUT là một số duy nhất ghi 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ụ: WORK.INP WORK.OUT 5 2 5 7 8 4 3 9 10 10 17 HD: Gọi dp[i] là thời gian ít nhất để i công nhân đầu tiên hoàn thành công việc của mình. Suy ra dp[n] là kết quả của bài toán Bài toán con nhỏ nhất: dp[0] = 0, nếu không có công nhân nào thì thời gian hoàn thành là 0 dp[1] = t[1], nếu chỉ có 1 công nhân làm việc thì thời gian hoàn thành chính là thời gian của công nhân đó. Xét công nhân thứ i: - Nếu công nhân thứ i tự làm công việc của mình thì thời gian hoàn thành của i công việc đầu tiên là: dp[i] = dp[i-1] + t[i] - Nếu công nhân I phối hợp với công nhân i-1 thì thời gian hoàn thành của i công nhân đầu tiên là: dp[i] = dp[i-2] + p[i-1] Vì cần hoàn thiện của I công nhân đầu tiên trong thời gian sớm nhất nên: dp[i] = min(dp[i-1] + t[i], dp[i-2] + p[i-1]) code c++