algorithm - Dynamic programming, minimizing cost? -

I came to this question:

You have N block A car that runs on 0 ends in block and block in a city at N - 1 . Each block i has a gas station which blocks the blocks from block to X [i] miles west of the block and y [I] In the east of the block, the MIL gas station only provides you when the initial amount is paid C [i] . Assume that all blocks lie on a straight road, give an algorithm that chooses to pay gas stations so that the cash given to gas stations is reduced and at least one gas station is transported everywhere on the road.

I tried:

• Brush force - tried all possible combinations and got the best one - worked perfectly but it took a lot of time.
• Greedy - I tried to be greedy at cost 1) Cover distance 2) Distance per cost

After a huge struggle, I concluded that this is probably a dynamic programming problem.

Trying for dynamic programming - I tried to come up with a repetition, not exactly the result, the hardest part I had found was that the station prevents both sides. To overcome it, I decided that I would move the stations to the highest in the West and in the past I will raise the amount by the same amount - can not continue.

I find a similar question, are these questions really similar?

Can anyone tell me what it is actually is a dynamic programming problem and there is no other way to do it more efficiently? If this is a dynamic programming then can you please give some suggestions about how I can go about this?

Example:

  Suppose N4 blocks 0: X = 1, Y = 1, C = 2 block 1: X = 0, Y = 2, C = 1 block 2: x = 2, y = 2, c = 5 block 3: x = 1, y = 5, c = 7 then the result will be, pay block 0, 1 gas station. Minimum Cost: 3  

As I understand, we want the minimum cost set Gas stations that will cover all the blocks. This can be prepared as the shortest path problem in the following article. Create an artificial source, an artificial sync, and a peak for each gas station. i & lt; J , i in the gas station is an arch for the th gas station and if only there is no difference in their coverage, each in the artificial source The arc for the gas station, which covers the block 0 , is the arc from each gas station of the artificial sync which covers the block n-1 . The cost of each arc is the cost of gas station on its head (Find 0 ) for the artificial sync from the source to the shortest route; The routes on which we travel are the gas stations we should buy coverage.

Time to run O (n ^ 2) Normal linear time is at least the path algorithm for the escalated guided graph. Probably is the improvement in o (n) ; See. (Yuval specifies O (n log n) time, but that's just because he is working in a different model of calculation, where sorting is omega (n log n) < / Code>.)