Cắt Thanh Gỗ Tối Ưu
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một thợ mộc có một thanh gỗ dài $N$ đơn vị và bảng giá bán các đoạn gỗ: đoạn có độ dài nguyên $i$ ($1 \le i \le N$) được bán với giá $p_i$. Anh ta có thể cắt thanh gỗ thành nhiều đoạn có độ dài nguyên dương (hoặc giữ nguyên không cắt) để bán. Hãy tìm tổng số tiền lớn nhất thu được.
Cấu trúc con tối ưu: $dp[i] = \max_{1 \le k \le i} (p_k + dp[i - k])$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 5000$).
- Dòng thứ hai chứa $N$ số nguyên $p_1, p_2, \dots, p_N$ ($0 \le p_i \le 10^9$).
Dữ liệu ra
- In ra tổng giá trị lớn nhất có thể thu được.
Ví dụ
| Input | Output |
|---|---|
| 4\n1 5 8 9 | 10 |
| 5\n2 5 7 8 10 | 12 |
Giới hạn
- $1 \le N \le 5000$
- $0 \le p_i \le 10^9$
Community Discussion