【题目描述】

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;  }