弗莱

用户名：1435075261

访问量：6013

签　名：

马梅，我还喜欢你，是不是有点可笑

等　　级
排　　名	1189
经　　验	2985
参赛次数	0
文章发表	27
年　　龄	0
在职情况	学生
学　　校	野鸡大学
专　　业

　　自我简介：

TA的其他文章

编写题解 1436: 蓝桥杯2014年第五届真题-地宫取宝 dfs vs dp
浏览：82

1282: 公交汽车 dfs vs dp
浏览：58

1499: 蓝桥杯算法提高VIP-分分钟的碎碎念 dp与dfs的无规则结合使用（巧解）
浏览：212

你可能喜欢

1282: 公交汽车 dfs vs dp

　　作者: 弗莱　　　　发表时间：2022-07-04 22:35:32 浏览：58　|　评论：0　

原题链接：公交汽车

### 这题比较简单，我采用了两种常见的方法来解答：
## 1：dfs(深度优先这题不可取，因为会时间超限87%)
`其实这题用dfs的思想十分好理解——最优解型模板（参考[我的博客](https://blog.csdn.net/weixin_55439495/article/details/125555660?spm=1001.2014.3001.5501 "我的博客")），即直接爆搜所有的可能，然后找到最优解，代码如下：`
    #include<stdio.h>
    int a[12]={0};
    int kl;
    int min=0;
    void dfs(int L,int p)
    {
    	if(L==kl)//终止条件
    	{
    		if(min>p)
    		{
    			min=p;//寻找最优解
    	    }
    	}
    	else if(L>kl)//越界剪枝
    	{
    		return;
    	}
    	else//显然不需要回溯
    	{
    			for(int i=1;i<=10;i++)
    			{
    				dfs(L+i,p+a[i]);	
    			}	
    	}
    
    }
    int main()
    {
    	for(int i=1;i<=10;i++)
    	{
    		scanf("%d",&a[i]);
    		min+=a[i];
    	}
    	scanf("%d",&kl);
    	dfs(0,0);//初始公里数和价格 
    	printf("%d\n",min);
    	return 0; 
    }

## 2:dp（动态规划）

这几天在反复的练习dfs和dp,dp思想掌握的还不太熟练，但是我总结了如下几点

`1：dp先当于dfs的进阶，能用dfs解的题（尤其是超时的题），一般可以通过动态规划写出来`
`2：dp先当与用空间换时间，一般情况下空间开销会比dfs大很多`

这题的dp比较容易找到思路：

1：初始值的设置（考虑到两个值即0公里0元，和1公里固定的费用）
        jyt[0]=0;
        jyt[1]=b[1];
    
    2:要如何找到最小的方案呢？
        拿题目举例，我们要知道行驶15公里的最小开销，而15可以有（0 15）（1，14）（2，13）（3，12）...这一系列方案组成，相当于我们又要知道每个组成他的方案的公里数的最小开销的值，以此类推，思路就出来了。
       相当于我们已经知道了行驶0公里和行驶1公里的最小开销，要根据这依次推出行驶2公里的最小开销，再推出行驶3公里的最小开销.....最终得到15公里的最小开销。
    
    3：要注意的点：
        a:公里数<=10时，当方案中出现0公里时(0+i=n)，这个方案的开销就是b[i];
        b:公里数>10时，不存在含0的方案，此时，对应地方的方案要用一个比较大的数来填充；
      
代码如下：
    #include<stdio.h>
    int a[102][102]={0};//方案矩阵
    int b[102]={0};//车费数组
    int kl;
    int jyt[102]={0};//记录每公里最小开销的数组
    int max=0;//填充值
    void dp()
    {
    	jyt[0]=0;//初值设置
    	jyt[1]=b[1];
    	for(int i=2;i<=kl;i++)//行驶的公里数
    	{
    		    int index=0;
    			//获取可行方案
    			for(int j=0;j<=i;j++)
    			{
    				for(int k=0;k<=i;k++)
    				{
    					if(j+k==i)
    					{
    						if((j==0&&k==i)||(j==i&&k==0))
    						{
    							if(i<=10)//小于10公里的处理
    							{
    								a[i][index]=b[i];
    							}
    							else//大于10公里的处理
    							{
    								a[i][index]=max;
    							}
    						}
    						else{
    							a[i][index]=jyt[k]+jyt[j];
    						}
    						//printf("%d ",a[i][index]);
    						index++;
    						
    											
    					}
    				}
    			}
    			//printf("\n");
    			jyt[i]=a[i][0];//寻找对应公里的最小开销并记录
    			for(int e=1;e<index;e++)
    			{
    				if(jyt[i]>a[i][e])
    				{
    					jyt[i]=a[i][e];
    				}
    			}
    	}
    //最后得到的jyt[kl]即是开kl公里对应的最小开销
    }
    
    int main()
    {
    	for(int i=1;i<=10;i++)
    	{
    		scanf("%d",&b[i]);
    		max+=b[i];
    	}
    	scanf("%d",&kl);
    	dp();
    	printf("%d\n",jyt[kl]);
    	return 0;
    }

0.0分

0 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

弗莱

TA的其他文章

你可能喜欢

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

Hello, world! （Java代码）

C语言训练-立方和不等式（C语言代码）

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

C二级辅导-统计字符（C语言代码）

1282: 公交汽车 dfs vs dp

评论区

精彩推荐

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

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

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

高精度加法（C++代码）（大数加法）

C二级辅导-公约公倍（C语言代码）

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

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

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

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

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

弗莱

TA的其他文章

你可能喜欢

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

Hello, world! （Java代码）

C语言训练-立方和不等式 （C语言代码）

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

C二级辅导-统计字符 （C语言代码）

1282: 公交汽车 dfs vs dp

评论区

精彩推荐

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

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

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

高精度加法 （C++代码）（大数加法）

C二级辅导-公约公倍 （C语言代码）

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

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

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

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

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

C语言训练-立方和不等式（C语言代码）

C二级辅导-统计字符（C语言代码）

　　评论区

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

高精度加法（C++代码）（大数加法）

C二级辅导-公约公倍（C语言代码）