绿色出行（green）

Question

绿色出行(green):为了保护环境，倡导“绿色出行”，小L每天都乘公共汽车上、下学。
WH城市的公共汽车很特别，没有一辆公共汽车行驶超过10公里(但都是行驶整数公
里)，所有街道在每公里处都有一个公共汽车站。一位顾客打算乘坐公共汽车行驶x公
里，他可以通过多次的换乘车来完成他的旅程，顾客每次换乘车都根据他所乘坐的公
里数来付费。小L的家和学校都恰好在公共汽车站处，相距n公里。小L是学生，在保护环境的同时当然忠要节省，他在想怎样换乘公共汽车，使得行驶n公里乘坐公共汽车的总费用最少。
第一行十个整数分别表示行走1到10公里的费用(费用≤500)。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶1公里的少。
第二行一个整数n表示，表示小L要乘坐的总路程数。
Output
仅一行包含一个整数，表示最少的费用。1sns100。
Sample Input
12 21 31 40 49 58 69 79 90 101
15
Sample Output
147
Sample Exp lanation
动态规划

Answer 1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    int cost[10]; // 存储行驶1到10公里的费用
    int n; // 总路程数
    int dp[1005]; // dp数组，dp[i]表示行驶i公里的最小花费
    memset(dp, INF, sizeof(dp)); // 初始化为最大值，表示不可达

    for (int i = 0; i < 10; i++) {
        cin >> cost[i];
    }
    cin >> n;

    dp[0] = 0; // 起点为0公里，花费为0

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 10 && j <= i; j++) { // 从1到10公里选择一个乘车距离
            dp[i] = min(dp[i], dp[i-j] + cost[j-1]); // 转移方程
        }
    }

    cout << dp[n] << endl; // 输出结果

    return 0;
}