Loading...
Loading...
Loading...
At the college fest, Asha plays a balloon game. There are n balloons in a row, and each balloon has a number on it.
When she bursts a balloon, she gets coins equal to its number times the numbers of the two balloons right next to it at that moment. If there is no balloon on one side, that side counts as 1. After a burst, the two neighbours of that balloon become next to each other.
Asha bursts all n balloons, one at a time, in any order she likes. Print the most coins she can collect.
long.Example 1
Input
4 3 1 5 8
Output
167
Burst 1 (3 × 1 × 5 = 15), then 5 (3 × 5 × 8 = 120), then 3 (1 × 3 × 8 = 24), then 8 (1 × 8 × 1 = 8). The total is 167, and no order does better.
Example 2
Input
2 1 5
Output
10
Bursting 1 first gives 1 × 1 × 5 = 5, then 5 alone gives 5, so 10. Bursting 5 first gives only 5 + 1 = 6.
Try the problem first. Open one hint at a time.
Trying every order is far too slow for 300 balloons. Look at one stretch of balloons from position left to position right instead.
Think about the balloon in that stretch that is burst last. At that moment its neighbours are the balloons just outside the stretch, which are still there.
Put a balloon with 1 at each end. Then best[left][right] is the largest of best[left][k - 1] + best[k + 1][right] + p[left - 1] × p[k] × p[right + 1], over every k from left to right.
Fill the table by the length of the stretch, from 1 up to n, so the shorter stretches are ready first.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor