Cắt Thanh Gỗ Theo Vết Định Sẵn
Points
33
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một thanh gỗ dài $L$ đơn vị (từ tọa độ $0$ đến $L$) và $K$ vị trí cần cắt phân biệt $c_1, c_2, \dots, c_K$ ($0 < c_i < L$). Mỗi lần thực hiện cắt một đoạn gỗ có độ dài $d$, bạn phải trả chi phí đúng bằng $d$.
Bạn có thể chọn thứ tự thực hiện $K$ nhát cắt sao cho tổng chi phí là nhỏ nhất. Hãy tìm tổng chi phí nhỏ nhất đó.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $L$ và $K$ ($2 \le L \le 10^6$, $1 \le K \le 100$).
- Dòng thứ hai chứa $K$ số nguyên phân biệt $c_1, \dots, c_K$ ($1 \le c_i < L$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 7 4\n1 3 4 5 | 16 |
| 9 5\n5 6 1 4 2 | 22 |
Giới hạn
- $2 \le L \le 10^6$
- $1 \le K \le 100$
Community Discussion