网页设计与网站建设在线第二章,软件网站开发公司,微信公众号网页设计,兰州企业 网站建设蓝桥杯上岸每日N题 第七期(小猫爬山)#xff01;#xff01;#xff01;
同步收录 #x1f447;
蓝桥杯上岸必背#xff01;#xff01;#xff01;(第四期DFS)
大家好 我是寸铁#x1f4aa;
冲刺蓝桥杯省一模板大全来啦 #x1f525;
蓝桥杯4月8号就要开始了
同步收录
蓝桥杯上岸必背(第四期DFS)
大家好 我是寸铁
冲刺蓝桥杯省一模板大全来啦
蓝桥杯4月8号就要开始了
距离蓝桥杯省赛倒数第3天 ❗️ ❗️ ❗️
还没背熟模板的伙伴们背起来
真题千千万万遍蓝桥省一自然现 ✌️
日更3000里蓝桥眷顾你
暴力出奇迹打表过样例
祝大家4月8号蓝桥杯上岸 ☀️
不清楚蓝桥杯考什么的点点下方
考点秘籍
想背纯享模版的伙伴们点点下方
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全第二期
蓝桥杯省一你一定不能错过的模板大全第三期
蓝桥杯省一你一定不能错过的模板大全第四期
想背注释模版的伙伴们点点下方
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)
蓝桥杯上岸每日N题第一期(二)
蓝桥杯上岸每日N题第一期(三)
蓝桥杯上岸每日N题第二期(一)
蓝桥杯上岸每日N题第三期(一)
蓝桥杯上岸每日N题 第四期(最少刷题数)
蓝桥杯上岸每日N题 第五期(山)
蓝桥杯上岸每日N题 第六期(求阶乘)
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句期末冲刺
想看JavaB组填空题的伙伴们点点下方
填空题
竞赛干货
算法竞赛字符串常用操作大全
蓝桥杯上岸必刷(模拟/枚举专题)
蓝桥杯上岸必背 (第三期 DP)
蓝桥杯上岸必背(第四期DFS)
蓝桥杯上岸必背(第五期BFS)
蓝桥杯上岸必背(第六期树与图的遍历)
蓝桥杯上岸必背(第七期 最短路算法)
蓝桥杯上岸必背(第八期 简单数论) 喜欢的小伙伴可以关注我关注寸铁我们一起上岸4.8蓝桥杯
小猫爬山
考点DFS可行性剪枝
分析
要尽可能减少花费--递归的分支尽可能少--优先考虑放重猫 优先考虑放重猫需要从大到小排个序 一直往下搜索答案是唯一的。 放得下猫就继续往该车往下加 放不下就再另外开一辆放猫 分两个分支去放 开一辆继续放其他猫的为一个分支 开另一辆单独只放一只猫的为另一个分支 接下来递归调用处理对于每个分支递归后有又n个分支一直递归下去直至递归到n层。说明当前的车数为最优解。 我们可以建立如下递归搜索图
DFS小结
递归DFS最简单直接的理解方式就是按照你的做题逻辑顺序来写 所以做题的逻辑顺序至关重要确保不重不漏地确保方案。 逻辑正确跑出来答案正确即可不要过分地去深究内在实现会很纠结。 注意dfs下一层要恢复现场这是必需的。 深究不外乎递归下一层置false回溯上一层用去掉无用的分支剪枝
Accode
//从大到小排个序优先放重猫。
//一直往下搜索答案是唯一的。
//放得下猫就继续往下加
//放不下就再另外开一辆继续放
//分两个分支去放
//开一辆继续放其他猫的有一个分支
//开另一辆只放一只猫的也有一个分支
import java.util.*;
public class Main{static int N20;static int n,m;static int arr[]new int [N];static int ansN;static int car[]new int [N];static int cat[]new int[N];public static void main(String []args){Scanner in new Scanner(System.in);nin.nextInt();min.nextInt();for(int i0;in;i)cat[i]in.nextInt();Arrays.sort(arr,0,n);//从小到大排个序Reverse(arr,0,n-1);//再从大到小排个序优先放重猫dfs(0,0);System.out.println(ans);}//直接把他看成是第一遍模拟剩下的递归处理即可。public static void dfs(int u,int k){if(kans)return;if(un){//走到n时即为找到答案ans当前小车的数量kansk;return;}//考虑猫都放一辆车的情况for(int i0;ik;i){if(cat[u]car[i]m){car[i]cat[u];dfs(u1,k);car[i]-cat[u];//恢复现场,便于下一次加猫操作}}//考虑猫只放一辆车的情况car[k]cat[u];dfs(u1,k1);//每次dfs会用到一辆车所以需要加一。car[k]0;//恢复现场}public static void Reverse(int q[],int l,int r)//反转函数 --从大到小排个序{for(int il,jr;ij;i,j--){int temparr[i];arr[i]arr[j];arr[j]temp;}}}✨ ✨ ✨ 看到这里不妨点个关注
