Cắt Thanh Gỗ Theo Vết Định Sẵn

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
33
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved