Giúp đỡ bài tập Quy hoạch động NKCABLE - nối mạng

newpie · March 7, 2021, 12:41pm

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.

Dữ liệu

Dòng đầu tiên chứa số lượng máy N (1 ≤ N ≤ 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á 106.
Kết quả

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

Ví dụ

Input:
6
2
2
3
2
2

Output:
7

Mấy bạn giải thích giùm mình cái yêu cầu với?

programmerit · July 22, 2015, 4:18pm

Theo mình ở đây họ không đòi hỏi liên thông.
Ở ví dụ trên
M1 — M2 = 2
M2 — M3 = 2
M3 — M4 = 3
M4 — M5 = 2
M5 — M6 = 2
Như vậy, mình có 1 lời giải như sau:
M1 nối với M2 mất 2 đơn vị
M3 nối M4 mất 3 đơn vị
M5 nối với M6 mất 2 đơn vị
Tổng cộng độ dài của cap cần thiết là 7.
Có lẽ bài toán này sử dụng phương pháp quy hoạch động thì sẽ giải được (ý kiến cá nhân)

Rok_Hoang · July 22, 2015, 5:32pm

Bài này mình có thể nhận ra là, máy i sẽ chỉ nối với máy i+1 hoặc máy i-1 (nếu ở 2 rìa thì 1 trong 2 thôi).
Lập bảng quy hoạch động là tính được:
L[i] = min(L[i-1],L[i-2])+M[i-1]. trong đó L[2]=M[1], L[3]=M[2]+M[1]. L[i] là độ dài dây nhỏ nhất nối từ 1->i.
Nếu cần nối thêm máy N vào N-1 máy trước thì có thể chọn nối máy 1->N-1 hoặc 1->N-2, rồi nối thêm máy N vào máy N-1.