Nối mạng

View as PDF
Submit solution
Points: 0.07 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
VNOI Marathon '08 - Practice Round
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ ~1~ đến ~N~ theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Input

  • Dòng đầu tiên chứa số lượng máy ~N~ ~(1 \leq N \leq 25000)~.
  • Dòng thứ ~i~ trong số ~N-1~ dòng tiếp theo chứa các khoảng cách từ máy ~i~ đến máy ~i+1~ ~(i = 1~, ~2~, ..., ~N-1)~. Giả thiết rằng khoảng cách từ máy ~1~ đến máy ~N~ không vượt quá ~10^{6}~.

Output

Ghi ra độ dài của cáp nối cần sử dụng.

Sample Input

6
2
2
3
2
2

Sample Output

7

Comments

Please read the guidelines before commenting.


  • 1
    ijk  commented on Dec. 31, 2024, 9:23 a.m. ← edit 3

    Sol mang tính chất tham khảo

    Gọi ~dp[i][j]~ là chi phí tối ưu nhất khi xét đến khoảng cách thứ ~i~ (~i=1...N, j=0...1~)

    Phát biểu lại bài toán: Chọn các khoảng cách sao cho tối ưu nhất và không có hai khoảng cách liên tiếp nào không được chọn

    Vì luôn phải chọn khoảng cách ~a[1]~ và ~a[n-1]~ nên ~dp[1][j]=a[1]~ và đáp án là ~a[n-1]+min(dp[n-2][j])~

    Xét khoảng cách ~i=2...n-2~:

    Nếu không chọn ~i~: ~dp[i][0]=dp[i-1][1]~

    Nếu chọn ~i~: ~dp[i][1]=min(dp[i-1][j])+a[i]~


  • 0
    minzdapoet1102  commented on Aug. 21, 2024, 5:49 a.m.

    Xin nhờ mọi người cho mình một chút gợi ý ạ!


  • 0
    Hiiragi_Sergan  commented on Sept. 18, 2023, 11:05 a.m.

    cần người giải thích input :(


    • 19
      catlover  commented on Oct. 26, 2023, 12:49 p.m.

      Test ví dụ dùng 3 đoạn cáp:

      • Nối máy 1 và 2 dùng đoạn độ dài 2
      • Nối máy 3 và 4 dùng đoạn độ dài 3
      • Nối máy 5 và 6 dùng đoạn độ dài 2

      • 0
        minhtrivy09  commented on July 22, 2024, 7:33 p.m. ← edited

        test ví dụ có 5 máy thôi mà bn? //e hiểu nhầm đề ạ e xin lỗi :)


      • -6
        Quangdpm  commented on Dec. 24, 2023, 2:31 a.m.

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


        • -5
          khoatri  commented on Dec. 24, 2023, 11:46 a.m.

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


  • -61
    thanh20092007  commented on May 31, 2023, 3:09 a.m. ← edit 2

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


  • -4
    Kiet76254  commented on Feb. 3, 2023, 9:29 a.m.

    Ai đó giải thích hộ mình cái same in out được không chứ mình chưa hiểu sao lại là 7 được nhỉ:??


  • 0
    kirito6725  commented on Aug. 24, 2022, 9:52 a.m.

    mấy bài này hay thật