Cutting Sticks |
It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price.
Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.
The next line consists of n positive numbers ci ( 0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order.
An input case with l = 0 will represent the end of the input.
100 3 25 50 75 10 4 4 5 7 8 0
The minimum cutting is 200. The minimum cutting is 22.