203 (POTHOLE) - Potholers
Compute the minimal cost of breaking the whole chocolate into single squares.
After careful observation you can see that you must always choose line with highest cost. Explanation for this is: Every time you choose to break a chocolate the cost of next breaks will increase, so it's pretty clear that we must first break the lines with highest cost.
The next observation is that, if equals , it doesn't matter which one you choose because the sum of these breaks will be the same. To see why this is true lets look at this example: Input:
2 2 2 2
As you can see equals . If you choose to break first the total cost will be '2 + 2*2', and the same will go for if you decide to break first. So the final conclusion is that cost of vertical breaking is:
And the same goes for horizontal breaks:
1 6 4 2 1 3 1 4 4 1 2