Work

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: WORK.INP
Output: WORK.OUT
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong ~1~ 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 ~1~ 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 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.

Input

Vào từ file văn bản WORK.INP:

  • Dòng thứ nhất ghi số ~N~ (~1 \le N \le 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 truyền ~t_1, t_2, ..., t_N~ (~1 \le t_i \le 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 ~p_1, p_2, ..., p_{N-1}~ (~1 \le p_i \le 100~)

Output

Ghi ra file WORK.OUT là ~1~ 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.

Sample Input 1

5
2 5 7 8 4
3 9 10 10

Sample Output 1

17

Comments

Please read the guidelines before commenting.


  • 0
    vogiahung05102011  commented on Nov. 21, 2025, 2:46 p.m.

    hello


  • 6
    m1nkpk4nn  commented on Aug. 10, 2025, 8:05 a.m.

    Bài y hệt tương tự.


    • -16
      quangvukts  commented on Sept. 1, 2025, 2:10 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 7
    quangthenpc  commented on April 4, 2025, 11:24 a.m. ← edit 7

    Spoiler

    Tạo một mảng dp[i] là thời gian tối thiểu để hoàn thành công việc của i người (ở đây mình sẽ coi như người thứ i nhờ người thứ i-1 làm chung).

    Để tìm được dp[i] thì ta có 2 lựa chọn:

    • Tự làm: dp[i] = dp[i - 1] + t[i]
    • Làm chung với người i-1: dp[i] = dp[i - 2] + p[i] (vì người i-1 đã hoàn thành xong việc ở bước trước)

    Nói cách khác: dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + p[i])

    Code: https://onlinegdb.com/cpRelvBB0

    Cài đặt bước đầu: dp[1] = t[1].

    Ở đây mảng p được nhập từ chỉ số 2.


    • 4
      khoangvan46  commented on April 5, 2025, 5:22 p.m.

      dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + p[i-1]) mới đúng chứ b


      • 0
        quangthenpc  commented on April 6, 2025, 2:14 a.m.

        Tại tui input mảng p từ 2 trở đi á, để tui ghi chú thêm. Cảm ơn nha.