【PTA】最小开销

2021-09-16 10:40:41 浏览数 (1)

6-2 最小开销 (10 分)

从起点到终点分布有N个驿站(驿站提供食宿,加满油,停车,检修等全套服务,按车收费,不提供分项服务)。假定汽车加满油及检修正常后,最多只能连续安全地跑两个驿站(即最多跳过一个)。请编写函数,计算对于给定的驿站及收费(N个驿站中,第i个驿站的收费标准是w[i])计算加满油从起点出发,到达终点的最小开销。

函数接口定义: int fun ( int *w,int N );

输入样例1: 第一行一个正整数N,表示起点和终点间驿站的个数,第二行是空格分隔的N个正整数,表示每个驿站的收费。

4 1 2 4 8

输出样例1: 计算最小的开销,本例中,经:第1,第3驿站,直达终点。最小开销是5。

5

输入样例2: 第一行一个正整数N,表示起点和终点间驿站的个数,第二行是空格分隔的N个正整数,表示每个驿站的收费。

10 10 80 10 10 90 10 10 10 100 10

输出样例2: 计算最小的开销,本例中,经:第1,第3,第4,第6,第8,第10驿站,直达终点。最小开销是10 10 10 10 10 10=60。

60

代码语言:javascript复制
int fun ( int *w,int N ){
	int prev = 0, curr = 0;
    for (int i = 2; i <= N; i  ) {
	    int next = fmin(curr   w[i - 1], prev   w[i - 2]);
	    prev = curr;
	    curr = next;
    }
	return curr;
}

0 人点赞