首页 > 代码库 > Laoj P1288 最小乘车费用

Laoj P1288 最小乘车费用

2024-11-16 16:51:39   203人阅读

问题背景
简单线性DP
试题描述
假设某条街上每一公里就有一个公共汽车站，并且一种可能的乘车费用如下表：
公里数 1 2 3 4 5 6 7 8 9 10
费用 12 21 31 40 49 58 69 79 90 101
而任意一辆汽车从不行驶超过10公里。某人想乘车到达n公里远的地方，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。
注意：10公里的费用比1公里小的情况是允许的。
输入格式
共两行。第一行为10个不超过200的整数，依次表示行驶1~10公里的费用，相邻两数间用一个空格隔开；第二行为某人想要乘车的公里数（不超过20000的整数）。
输出格式
仅一行，包含一个整数，表示到达n公里所需要的最小费用。
输入示例
12 21 31 40 49 58 69 79 90 101
15
输出示例
147

【分析】

dp入门，水题。

【代码】

 1 #define mem(a, b, c) for(int i=1;i<=c;++i) a[i]=b;
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int n, a[20], dp[20020];
 6 
 7 int main() {
 8     for (int i=1;i<=10;++i)
 9         cin >> a[i];
10     cin >> n;
11     mem(dp, 0x7fffffff, n);
12     for (int i=1;i<=n;++i)
13         for (int j=1;j<=min(10, i);++j)
14             dp[i]=min(dp[i], dp[i-j]+a[j]);
15     cout << dp[n] << endl;
16 }

 

Laoj P1288 最小乘车费用


联系
我们