UVa 10003

Summary

This is a straightforward Dynamic Programming problem. The trick is to define the recurrence carefully.

Explanation

Since ${\displaystyle n}$ can be as large as 50, trying every ordering of cuts is well beyond feasible.

The concept behind the recurrence involves rephrasing it so that it can be answered with subproblems.

Given a series of locations to make the cuts and its borders, what is the cheapest way to make all the cuts? The answer is basically try everything and take the minimum - make a cut everywhere, and try to answer that subproblem that comes up.

So the function ${\displaystyle C(a_{1},a_{2},\ldots ,a_{n})}$ where ${\displaystyle a_{i}}$ are places where cuts are possible. In particular, ${\displaystyle a_{1}}$ and ${\displaystyle a_{n}}$ will serve as the end points, since it never makes sense to make a cut at an edge (and thus having the same problem).

When we make a cut at ${\displaystyle a_{i}}$, it gives us two subproblems - the left side, and the right side. With the base case ${\displaystyle C(a_{i},a_{i+1})=0}$ (which basically means if there is one board with no more cuts to be made, the cost is zero), we can now formulate the recurrence:

${\displaystyle C(a_{i},a_{j})=\min _{k\in (i+1,\ldots ,j-1)}\left[C(a_{i},a_{k})+C(a_{k},a_{j})\right]+cost(a_{i},a_{j})}$

The cost of making a cut is simply:

${\displaystyle cost(a_{i},a_{j})=a_{j}-a_{i}}$

Gotchas

The test input is huge on this program, so even being as efficient as possible you're going to have a hard time getting this one in under the time limit. I recommend allocating all of your arrays up front, and only clearing out their memory as necessary for test cases. It wasn't until I did this did I get this solution to run in time, and it still took a whopping 2.64 seconds.

Input

100
3
25 50 75
10
4
4 5 7 8
0


Output

The minimum cutting is 200.
The minimum cutting is 22.