【题解】公交乘车
【题目描述】
A城市有一条非常特别的街道，该街道在每个公里的节点上都有一个公交车站，乘客可以在任意的公交站点上车，在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费，比如，下表就是乘客乘坐不同的公里数要付的费用。（请注意：不一定公里数越高，费用越高，这也是这条街道特别的地方）
一辆公交车单次行驶的公里数一定不超过10公里，一个乘客如果打算乘坐公交车完成n公里（1<=n<=100）的行程，他可以选择无限次的换车来完成行程。
请问，他最少要花多少钱？
【输入描述】
第一行十个整数分别表示公交行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。
第二行一个整数n表示，旅客的总路程数。 （1<=n<=100）
【输出描述】
仅一个整数表示最少费用。
【样例输入】
12 21 31 40 49 58 69 79 90 101 15
【样例输出】
147
【题目分析】
我们需要计算行驶 n 公里的最小费用。公交公司提供的费用表如下：
行驶
1公里的费用为cost[0]。行驶
2公里的费用为cost[1]。...
行驶
10公里的费用为cost[9]。
目标是找到行驶 n 公里的最小费用。
动态规划的第一步是定义状态。状态需要能够描述问题的子问题，并且可以通过状态转移逐步求解原问题。
对于本问题：
设
dp[i]表示行驶i公里的最小费用。我们的目标是求
dp[n]。
为了求解 dp[i]，我们需要考虑如何通过更小的子问题来构造它。具体来说：
行驶
i公里的费用可以通过以下方式得到：先行驶
j公里，费用为cost[j - 1]。然后行驶剩下的
i - j公里，费用为dp[i - j]。因此，行驶
i公里的总费用为dp[i - j] + cost[j - 1]。
为了找到行驶 i 公里的最小费用，我们需要尝试所有可能的 j（从 1 到 10），并选择其中的最小值。因此，状态转移方程为：
dp[i] = min(dp[i], dp[i - j] + cost[j - 1]);
解释
dp[i]：当前行驶i公里的最小费用。dp[i - j]：行驶i - j公里的最小费用。cost[j - 1]：行驶j公里的费用。min(dp[i], dp[i - j] + cost[j - 1])：选择所有可能的j中的最小值。
【参考答案】
#include<bits/stdc++.h>
using namespace std;
int main() {
int cost[10]; // 输入1到10公里的费用
int dp[105]; // 初始化dp数组
for (int i = 0; i < 10; i++) {
cin >> cost[i];
}
// 输入总路程
int n;
cin >> n;
for (int i = 0; i <= n; i++) {
dp[i] = INT_MAX; // 初始化为不可达
}
dp[0] = 0; // 行驶0公里的费用为0
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 10; j++) {
if (i >= j && dp[i - j] != INT_MAX) {
dp[i] = min(dp[i], dp[i - j] + cost[j - 1]);
}
}
}
// 输出结果
cout << dp[n] << endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
