Bursting Balloons

Difficulty: 2100 6000 ms 128 MB

dp interval-dp

Balloons in a row hold values a_1..N. Bursting balloon i earns a_left·a_i·a_right, where left/right are the nearest UNBURST neighbours (value 1 beyond the ends). Maximize the total coins over all bursting orders.

Input: the first line has N; the second line has the N values.

Output: the maximum coins.

Constraints:

• 1 ≤ N ≤ 500
• 0 ≤ a_i ≤ 100

Sample Tests

4
3 1 5 8

167

1
5

5

Read the Editorial