SPOJ CHOCOLA

From Algorithmist
Jump to navigation Jump to search

203 (POTHOLE) - Potholers[edit]

Summary[edit]

Compute the minimal cost of breaking the whole chocolate into single squares.

Explanation[edit]

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:

Input[edit]

1

6 4
2
1
3
1
4
4
1
2

Output[edit]

42