Description: acm algorithm design
Description:
Top up after a car traveling n km. The road there are a number of gas stations. Design an effective algorithm, which should be pointed out that the gas station refueling stop to refuel along the least number.
For a given n and k the location of gas stations, refueling at least the number of computing programming.
Input:
The first line has two positive integers n and k, that the auto top up can be closed n-km journey in k and gas stations. 1 the next line, there are integers k+1, k that the first gas stations with the first
k-1 the distance between gas stations. 0 stations, said first point, the vehicles have top up. Filling the first k+1 that destination.
Output:
At least the number of refueling. If you can not reach their destinations, then output "No Solution!".
Cases of type:
7 7
1 2 3 4 5 1 6 6
Cases the output:
4
To Search:
File list (Check if you may need any files):
Oiling Car
..........\Debug
..........\.....\Oiling Car.exe
..........\.....\Oiling Car.ilk
..........\.....\Oiling Car.obj
..........\.....\Oiling Car.pch
..........\.....\Oiling Car.pdb
..........\.....\StdAfx.obj
..........\.....\vc60.idb
..........\.....\vc60.pdb
..........\Oiling Car.cpp
..........\Oiling Car.dsp
..........\Oiling Car.dsw
..........\Oiling Car.ncb
..........\Oiling Car.opt
..........\Oiling Car.plg
..........\ReadMe.txt
..........\StdAfx.cpp
..........\StdAfx.h
Download