Cắt thanh gỗ
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một thanh gỗ có độ dài $N$ và bảng giá $P_1, P_2, \dots, P_N$, trong đó $P_i$ là giá bán của một khúc gỗ có độ dài $i$. Bạn có thể cắt thanh gỗ thành các khúc có độ dài nguyên dương bất kỳ (hoặc không cắt).
Hãy tìm tổng số tiền bán gỗ lớn nhất có thể thu được.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 2000$).
- Dòng thứ hai chứa $N$ số nguyên $P_1, P_2, \dots, P_N$ ($1 \le P_i \le 10^9$).
Dữ liệu ra
Một số nguyên duy nhất là lợi nhuận tối đa.
Ví dụ
| Input | Output |
|---|---|
8<br>1 5 8 9 10 17 17 20 |
22 |
Giới hạn
- $1 \le N \le 2000$
- $1 \le P_i \le 10^9$
Community Discussion