题目1086：最小花费

题目描述： 在某条线路上有N个火车站，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3.其对应关系如下: 距离s           票价 0<S<=L1         C1 L1<S<=L2        C2 L2<S<=L3        C3 输入保证0<L1<L2<L3<10^9,0<C1<C2<C3<10^9。 每两个站之间的距离不超过L3。 当乘客要移动的两个站的距离大于L3的时候，可以选择从中间一个站下车，然后买票再上车，所以乘客整个过程中至少会买两张票。 现在给你一个 L1，L2，L3，C1，C2,C3。然后是A B的值，其分别为乘客旅程的起始站和终点站。 然后输入N，N为该线路上的总的火车站数目，然后输入N-1个整数，分别代表从该线路上的第一个站，到第2个站，第3个站，……，第N个站的距离。 根据输入，输出乘客从A到B站的最小花费。

输入： 以如下格式输入数据： L1  L2  L3  C1  C2  C3 A  B N a[2] a[3] …… a[N]

输出： 可能有多组测试数据，对于每一组数据， 根据输入，输出乘客从A到B站的最小花费。

样例输入： 1 2 3 1 2 3 1 2 2 2 样例输出： 2

使用动态规划

#include<stdio.h> #include<iostream> using namespace std; const int MAX = 1010; #define INF 0x7fffffffffff //设置这个最大值时要注意和long long型比较大小，这里并没有完全表示成longlong的最大值 long long getMin(long long a, long long b) { return a < b ? a : b; } int main() { int l1, l2, l3; int c1, c2, c3; int a, b, n; long long dis[MAX]; long long price[MAX]; while (cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3) { cin >> a >> b; if (a > b) { int tmp = a; a = b; b = tmp; } cin >> n; for (int i = 2; i <= n; i++) cin >> dis[i]; for (int i = b; i > a; i--) dis[i] -= dis[i - 1]; for (int i = a; i <= b; i++) price[i] = INF; price[a] = 0; for (int i = a + 1; i <= b; i++) { long long len = 0; for (int j = i - 1; j >= a; j--) { len += dis[j + 1]; if (len <= l1) price[i] = getMin(price[i], price[j] + c1); else if (len <= l2) price[i] = getMin(price[i], price[j] + c2); else if (len <= l3) price[i] = getMin(price[i], price[j] + c3); else break; } } cout << price[b] << endl; } return 0; }

题目链接：

http://ac.jobdu.com/problem.php?pid=1086

参考资料：

http://www.programgo.com/article/7202485252/