solution

Xưởng cơ khí có thanh thép dài $n$ mét. Có thể bán các đoạn dài tối đa $L$ mét, với bảng giá $price[1..L]$ — trong đó $price[j]$ là giá một đoạn dài $j$ mét. Hãy chọn cách cắt để tổng doanh thu lớn nhất.

Dùng DP: $dp[i] = \max_{1 \le j \le \min(L, i)} \{ dp[i-j] + price[j] \}$, với $dp[0] = 0$.

Ví dụ $n = 8$, $L = 4$, $price = [1, 5, 8, 9]$: cắt thành $2 + 3 + 3$ được $5 + 8 + 8 = 21$.