#447. DPCABLE – Nối cáp

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nhà Bờm có n máy tính xếp thẳng hàng (cố định) được đánh số từ 1 đến n . Bờm muốn nối các máy tính lại với nhau sao cho mỗi máy tính được nối với ít nhất một máy tính khác. Biết khoảng cách giữa hai máy liên tiếp thứ i và thứ i + 1 d_i (i = 1, 2, …, n – 1) . Em hãy giúp Bờm tính xem tổng độ dài dây cáp ít nhất Bờm cần phải sử dụng nhé.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương n ;
  • Dòng thứ hai chứa n - 1 số nguyên dương d_1, d_2, …, d_{n - 1} .

Dữ liệu ra:

  • Một số nguyên duy nhất là tổng độ dài dây cáp Bờm cần dùng.

Ví dụ:

Dữ liệu vào:
6
2 2 3 2 2
Dữ liệu ra:
7
Giải thích:
Cách nối máy của Bờm

Giới hạn:

  • 1 ≤ N ≤ 25000; 1 ≤ d_i < 10^4 .