daily

用户名：weightless

访问量：1202

签　名：

Hello world！

等　　级
排　　名	11157
经　　验	1004
参赛次数	5
文章发表	2
年　　龄	15
在职情况	学生
学　　校	绍兴鲁迅中学
专　　业

　　自我简介：

热爱计算机，目前正处于入门阶段（QQ号 3205177338）

TA的其他文章

最大体积（动态规划补空隙C++）
浏览：396

你可能喜欢

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

优质题解

公交汽车（C++）

　　作者: daily　　　　发表时间：2022-02-07 20:26:33 浏览：627　|　评论：0　

原题链接：公交汽车

- 定义变量
题目中说明有需要10个整数代表不同路程的费用，于是先声明一个数组（名为worth，长度为11，worth[0]为空，worth[1~10]表示一次性行走1~10公里所需费用）
接着定义dp数组（dp[0] = 0），下标i为走过的总路程，dp[i]表示走过i公里所需的最小费用。
- 求递推式
要走过i公里的路程，就需要分两步走，第一步是走i-j公里的路程，第二步是走j公里的路程（j <= i <= n（总路程）, 0 <= j <= s（当i<=10时，s=i；否则s=10，下同））那么走过i公里的最小费用就是走过i-j公里的最小费用加上一次性走j公里所需的费用。
所以，令i从1到n循环，并将dp[i]初始化为INF=500*100+1=50001，以便比较得出最小值，再在这个循环中令j从1到s循环（当j=0时dp[i]=dp[i]+0可以省去），最里层不断比较dp[i]和dp[i-j]+worth[j]的大小并取小者储存于dp[i]中。
由此得到递推式：
> dp[i] = min{dp[i-j] + worth[j], dp[i]}
- 代码说明
以下代码中MAX为最大总路程+1，A_JOURNEY为公共汽车一次性能行走的最大路程，INF用来初始化dp数组以便比较取最小费用。

```cpp
#include<iostream>
#define MAX 101
#define INF 50001
#define A_JOURNEY 10
using namespace std;
inline int min(int a, int b) {
	return a < b ? a : b;
}

int dp[MAX];

int main() {
	int n, worth[A_JOURNEY + 1];
	for(int i = 1; i <= A_JOURNEY; i++)  //读入数据
		scanf("%d", worth + i);
	scanf("%d", &n);

for(int i = 1; i <= n; i++) { //i表示总路程
		dp[i] = INF;
		for(int j = 1; j <= (i <= A_JOURNEY ? i : A_JOURNEY);
		        j++)  //j表示这班车走的路程
			dp[i] = min(dp[i - j] + worth[j],
			            dp[i]);  //dp[i]表示走i公里路程所需的最少费用
	}
	printf("%d", dp[n]);
	return 0;
}
```
PS：本人不善于言辞，请多指教。

0.0分

19 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

daily

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

C二级辅导-温度转换（C语言代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

公交汽车（C++）

评论区

精彩推荐

校门外的树（C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

关于C语言变量位置的问题

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

WU-数组替换（C++代码）

daily

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

C二级辅导-温度转换 （C语言代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

公交汽车（C++）

评论区

精彩推荐

校门外的树 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

关于C语言变量位置的问题

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

WU-数组替换 （C++代码）

C二级辅导-温度转换（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

　　评论区

校门外的树（C语言代码）

WU-数组替换（C++代码）