Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKCABLE - Nối mạng

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ụ

Dữ liệu:
6
2
2
3
2
2

Kết qủa
7

Được gửi lên bởi:Jimmy
Ngày:2008-01-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon '08 - Practice Round

hide comments
2015-02-20 12:24:04 Phạm Nhật Minh
0 diem la sao zay may bn?
2015-02-15 09:11:14 Bee
các bác xài longint hết là AC.
2014-10-27 12:29:38 Nguyễn A
f[i]:=min(f[i-2],f[i-1])+a[i-1]
2014-08-01 17:07:21 ■■‡[ND] Bee Sociu■■‡
Em Bee có nhìn công thức không vậy =)))))

Last edit: 2014-09-15 12:55:01
2014-03-31 16:45:38 Việt MrKid
giờ mới hiểu được cái đề :d!
đề nói là mỗi máy được nối với ít nhất 1 máy khác!
không nhất thiết tất cả các máy nối với nhau

1 - 2
3 - 4
5 - 6
2013-12-02 15:07:20 Xiao Lang
Duyệt trâu cũng AC @Trường...
2013-12-01 15:12:20 Human Immunodeficiency Virus
f[1]=0 (1 máy thì nối đến máy nào == )
f[2]=a[1] (có 2 máy thì nối với nhau )
f[3]=a[1]+a[2] (3 máy thì 3 máy nối với nhau
f[i]:=min(f[i-1],f[i-2])+a[i-1]
2013-11-25 13:55:17 Thã̀ng ngố
ĐỌC KĨ ĐỀ ĐI BẠN " mỗi máy được nối với ít nhất một máy khác" !!!
2013-11-03 15:52:07 Code Phát TLE luôn
Bài này làm thế nào thế ! :<
2013-09-22 08:49:26 I have LASER BEAMS !
f[i]:=min(f[i-2],f[i-1])+a[i] hay
f[i]:=min(f[i-2],f[i-1])+a[i-1] ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.