Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$
Draft saved