daily

用户名：weightless

访问量：1171

签　名：

Hello world！

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

　　自我简介：

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

TA的其他文章

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

你可能喜欢

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

优质题解

公交汽车（C++）

　　作者: daily　　　　发表时间：2022-02-07 20:26:33 浏览：611　|　评论：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语言程序设计教程（第三版）课后习题1.5 （C语言代码）

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

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

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

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

公交汽车（C++）

评论区

精彩推荐

简洁的代码

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

C语言考试练习题_保留字母（C语言代码）

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

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

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

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

打印十字图（C语言代码）

关于float，double变量的几点说明

模拟计算器（C语言代码）

daily

TA的其他文章

你可能喜欢

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

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

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

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

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

公交汽车（C++）

评论区

精彩推荐

简洁的代码

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

C语言考试练习题_保留字母 （C语言代码）

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

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

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

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

打印十字图 （C语言代码）

关于float，double变量的几点说明

模拟计算器 （C语言代码）

　　评论区

C语言考试练习题_保留字母（C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

打印十字图（C语言代码）

模拟计算器（C语言代码）