Building a Spaceship
InterviewTime limit2sMemory limit512 MB
Partition the ordered parts into contiguous groups, paying for each group the product of its maximum weight and maximum energy; minimize the total cost.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Array, Divide and conquer, Stack
- Solved
- No attempts yet
Problem
Star-Lord and Rocket are building a spaceship to rescue Thor.
To build the spaceship, they must buy all N parts from a shop. Every part has a weight W and an energy E. The shop arranges all parts in order from part 1 to part N and sells them that way.
This shop prices each part at W*E. It also sells in an unusual way: if you pay the product W_max *E_max of the maximum weight W_max and the maximum energy E_max among parts L through R, you can buy all parts from L to R at once. The shop also allows buying part X and part Y (X<Y) at the same time, or buying part X before part Y, but it does not allow buying part Y before part X.
Find the minimum cost for Star-Lord and Rocket to buy all the parts.
Input
The first line gives the number of parts N(1 ≤ N ≤ 1,000).
The second line gives the weight W(0 ≤ W ≤ 1,000,000) of each part.
The third line gives the energy E(0 ≤ E ≤ 1,000,000) of each part.
Output
Print the minimum cost for Star-Lord and Rocket to buy all the parts on one line.
Hint
In the second example, buying parts 1 and 2 together at a cost of 10 x 4, buying part 3 at a cost of 99, and buying parts 4 and 5 at a cost of 7x4 lets them buy all the parts for a total cost of 167.