蓝桥杯上岸每日N题 第七期(小猫爬山)！！！
同步收录 👇
蓝桥杯上岸必背！！！(第四期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回溯上一层用+去掉无用的分支剪枝文章来源：https://www.toymoban.com/news/detail-634000.html
Accode
//从大到小排个序，优先放重猫。
//一直往下搜索，答案是唯一的。
//放得下猫就继续往下加
//放不下就再另外开一辆，继续放
//分两个分支去放
//开一辆继续放其他猫的有一个分支
//开另一辆只放一只猫的也有一个分支
import java.util.*;
public class Main{
static int N=20;
static int n,m;
static int arr[]=new int [N];
static int ans=N;
static int car[]=new int [N];
static int cat[]=new int[N];
public static void main(String []args){
Scanner in = new Scanner(System.in);
n=in.nextInt();
m=in.nextInt();
for(int i=0;i<n;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(k>=ans)return;
if(u==n){
//走到n时，即为找到答案ans=当前小车的数量k
ans=k;
return;
}
//考虑猫都放一辆车的情况
for(int i=0;i<k;i++){
if(cat[u]+car[i]<=m){
car[i]+=cat[u];
dfs(u+1,k);
car[i]-=cat[u];
//恢复现场,便于下一次加猫操作
}
}
//考虑猫只放一辆车的情况
car[k]=cat[u];
dfs(u+1,k+1);
//每次dfs会用到一辆车，所以需要加一。
car[k]=0;
//恢复现场
}
public static void Reverse(int q[],int l,int r)
//反转函数 -->从大到小排个序
{
for(int i=l,j=r;i<j;i++,j--){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
✨ ✨ ✨
看到这里，不妨点个关注 💖文章来源地址https://www.toymoban.com/news/detail-634000.html
到了这里，关于蓝桥杯上岸每日N题 第七期(小猫爬山)！！！的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
