【正经题解】最小乘车费用

这问题是一个典型的动态规划问题。我们需要找到一种乘车方案使得费用最小。首先，我们定义一个一维数组 $dp$ ，其中 $dp$ [ $i$ ]表示行驶 $i$ 公里所需的最小费用。初始时，我们将 $dp$ [ $i$ ]初始化为 $i$ * $v$ [ $0$ ]，即按照 $1$ 公里的费用进行计算。
然后，我们使用两层循环来更新 $dp$ 数组。外层循环遍历每个行驶的公里数，内层循环遍历每个车程费用。在每次内层循环中，我们比较当前的最小费用 $dp$ [ $j$ ]和通过选择该车程费用所得到的费用 $dp$ [ $j$ $-$ $w$ [ $i$ ]] $+$ $v$ [ $i$ ]，取两者的较小值更新 $dp$ [ $j$ ]。
最终， $dp$ [ $m$ ]即为行驶 $m$ 公里所需的最小费用，输出该值即可。

#include<iostream>
#include<algorithm>

using namespace std;

int n = 10, m;
int w[15], v[15], dp[10000000];

int main() {
    // 读入费用描述
    for (int i = 0; i < 10; i++) {
        cin >> v[i];
        w[i] = i + 1;
    }

    // 读入目标行驶的公里数
    cin >> m;

    // 初始化dp数组
    for (int i = 0; i <= m; i++) {
        dp[i] = i * v[0];
    }

    // 动态规划计算最小费用
    for (int i = 0; i < 10; i++) {
        for (int j = w[i]; j <= m; j++) {
            dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // 输出结果
    cout << dp[m];

    return 0;
}