2364: 【入门】公交乘车

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：3

题目描述

A城市有一条非常特别的街道，该街道在每个公里的节点上都有一个公交车站，乘客可以在任意的公交站点上车，在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费，比如，下表就是乘客乘坐不同的公里数要付的费用。（请注意：不一定公里数越高，费用越高，这也是这条街道特别的地方）

公里数 1 2 3 4 5 6 7 8 9 10
付费金额 12 21 31 40 49 58 69 79 90 101

一辆公交车单次行驶的公里数一定不超过 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~10 公里；走 k 公里花费对应输入的费用。
  • 目标：凑齐总 n 公里，总花费最小。

状态定义： dp[i]：走完 i 公里 需要的最少花费。

转移方程： 对于每一个总里程i，尝试走 k 公里（k=1~10，i>=k）

\(dp[i]=\min(dp[i],\ dp[i-k] + cost[k])\)

初始化：

  • dp[0]=0：0 公里花费 0；
  • 其余 dp 数组初始化为很大的数（无穷大）。

cost [1] 是走 1 公里费用，cost [2] 走 2 公里……cost [10] 走 10 公里。 

#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int dp[MAXN];
int cost[11]; // cost[1]~cost[10]

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

    //初始化无穷大
    for(int i = 1; i <= n; i++)
        dp[i] = INF;
    dp[0] = 0;

    //完全背包
    for(int i = 1; i <= n; i++)
    {
        //尝试每一种单次乘车距离1~10
        for(int k = 1; k <= 10; k++)
        {
            if(i >= k)
            {
                dp[i] = min(dp[i], dp[i - k] + cost[k]);
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

来源/分类

提交提交记录统计露一手!