acm算法设计

描述：

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。

对于给定的n和k个加油站位置，编程计算最少加油次数。

输入：

第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第

k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。

输出：

的最少加油次数。如果无法到达目的地，则输出”No Solution!”。

例输入：

7 7

1 2 3 4 5 1 6 6

例输出：

4-acm algorithm design

Descr iption:

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