Rod Cutting
easyDynamic Programming II+10 XPTime limit 2s
A carpenter has a wooden rod of length n. A piece of length i sells for price[i] rupees. She may cut the rod into any number of pieces of whole lengths (or not cut it at all). What is the most money she can earn?
Input:
- line 1:
n - line 2:
nprices —price[1] … price[n]
Output: the maximum total price.
Constraints: 1 ≤ n ≤ 1000, 0 ≤ price ≤ 10⁶. The answer fits in a 64-bit integer.
Think about it: decide the first piece: if it has length k, the rest is the same problem for length n − k. So best[L] = max over k of price[k] + best[L − k], filled for L = 1 … n. O(n²).
Sample input 1
8 1 5 8 9 10 17 17 20
Sample output 1
22
Sample input 2
4 3 5 8 9
Sample output 2
12
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).