Cắt Thanh Gỗ Tối Ưu

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved