1349 - Signal Beacon
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 54
Solved: 21
- Description
- In a remote mountainous area, there are N mountains aligned in straight line. From left to right the ith mountain has height Hi. On each mountain live many plain residents. Now we want to place signal beacons on the peaks of these N mountains, in order for this area to be covered by cell phone signal. It costs Ci Yuan to place a beacon on the peak of the ith mountain. If a beacon is placed on the ith mountain, then the nearest mountain to the left and right of it which is not lower than it will block the signal sent to or from it. For example:
(H) = {1 4 5 6 7 2}, i.e. the first mountain has height 1, the second mountain has height 4 ……
If you place a beacon on the 1st mountain, then the signal can cover first two mountains: 1,2.
If you place a beacon on the 5th mountain, then the signal can cover all mountains.
If you place a beacon on the 3rd mountain, then the signal can cover first 4 mountains: 1, 2, 3, 4.
To make all the mountains covered by signal, what is the minimum total cost by placing signal beacons on some mountains?
- Input
- There are multiple cases.
The first line has a positive number: N (1<=N<=10000).
The second line contains N positive numbers, the ith number is Hi
(1<= Hi <=10^9), height of ith mountain. It is guaranteed that no two mountains have the same height.
The third line contains N positive numbers, the ith number is Ci (1<= Ci <=10^9)，cost of placing a beacon on ith mountain.
- Output
- Out put one line, the minimum total cost to cover all mountains with signal.
- sample input
-
3 1 2 3 1 2 3
- sample output
-
Case #1: 2
- hint
- source
- Liu Fei, HUST Campus 2009