Đóng Gói Kiện Hàng
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Trên băng chuyền có $N$ món hàng xếp thành một hàng, món hàng thứ $i$ có kích thước $w_i$. Bạn cần chia $N$ món hàng này thành các lô liên tiếp, mỗi lô chứa tối đa $K$ món hàng.
Chi phí đóng gói một lô gồm các món hàng từ $l$ đến $r$ là $C + \max_{l \le i \le r} w_i$, trong đó $C$ là chi phí cố định cho mỗi hộp.
Hãy tìm tổng chi phí đóng gói nhỏ nhất để đóng gói hết cả $N$ món hàng.
Dữ liệu vào
- Dòng đầu tiên gồm ba số nguyên $N, K, C$ ($1 \le K \le N \le 2000$, $0 \le C \le 10^9$).
- Dòng thứ hai gồm $N$ số nguyên $w_1, w_2, \dots, w_N$ ($1 \le w_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 5 2 10 3 8 2 7 4 |
47 |
Giới hạn
- $1 \le K \le N \le 2000$
- $0 \le C \le 10^9$, $1 \le w_i \le 10^9$
Community Discussion