Đóng Gói Lô Hàng
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Một nhà máy có $N$ kiện hàng xếp thành hàng ngang, kiện thứ $i$ có kích thước $a_i$. Nhà máy muốn chia $N$ kiện hàng này thành các lô liên tiếp để đóng gói.
Nếu một lô gồm các kiện hàng từ $j+1$ đến $i$ với tổng kích thước là $S = \sum_{k=j+1}^{i} a_k$, chi phí đóng gói lô đó là: \[(S - L)^2 + C\] trong đó $L$ là kích thước chuẩn và $C$ là chi phí cố định cho mỗi lô.
Hãy tìm tổng chi phí đóng gói nhỏ nhất để chia hết $N$ kiện hàng.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, L, C$ ($1 \le N \le 10^5$, $0 \le L \le 10^6$, $0 \le C \le 10^9$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 1000$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 5 2 2 3 4 1 |
4 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le a_i \le 1000$, $0 \le L \le 10^6$, $0 \le C \le 10^9$
Community Discussion