当前位置: 首页 > news >正文

165. 小猫爬山

Powered by:NEFU AB-IN

Link

文章目录

  • 165. 小猫爬山
    • 题意
    • 思路
    • 代码

165. 小猫爬山

  • 题意

    翰翰和达达饲养了 N只小猫,这天,小猫们要去爬山。
    经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。
    翰翰和达达只好花钱让它们坐索道下山。
    索道上的缆车最大承重量为 W,而 N只小猫的重量分别是 C1、C2……CN。
    当然,每辆缆车上的小猫的重量之和不能超过 W。
    每租用一辆缆车,翰翰和达达就要付 1美元,所以他们想知道,最少需要付多少美元才能把这 N只小猫都运送下山?

  • 思路

    可以看到n特别小,w特别大,所以不是一个背包问题,考虑爆搜
    DFS策略

    • 遍历目前开的所有车,若能放到这个车,就放
    • 若遍历完所有车都放不了,那么就开新车

    DFS剪枝

    • 如果车的数量比目前答案大了,return
    • 优先考虑决策少的,也就是分支少的节点,在此题中,重量大的更少被考虑,所以优先考虑重量大的,也就是事先降序排序
  • 代码

    /*
    * @Author: NEFU AB-IN
    * @Date: 2023-03-01 09:22:35
    * @FilePath: \Acwing\165\165.cpp
    * @LastEditTime: 2023-03-01 10:14:16
    */
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #undef int#define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
    #define DEBUG(X) cout << #X << ": " << X << '\n'
    typedef pair<int, int> PII;const int N = 20, INF = 0x3f3f3f3f;
    int c[N], sum[N];
    int n, w;
    int ans = INF;
    void dfs(int u, int k)
    {if (k >= ans)return;if (u == n + 1){ans = k;return;}for (int i = 0; i < k; ++i){if (c[u] + sum[i] <= w){sum[i] += c[u];dfs(u + 1, k);sum[i] -= c[u];}}sum[k] = c[u];dfs(u + 1, k + 1);sum[k] = 0;
    }signed main()
    {IOS;cin >> n >> w;for (int i = 1; i <= n; ++i){cin >> c[i];}sort(c + 1, c + 1 + n, greater<int>());dfs(1, 1);cout << ans << '\n';return 0;
    }
    

相关文章:

165. 小猫爬山

Powered by:NEFU AB-IN Link 文章目录165. 小猫爬山题意思路代码165. 小猫爬山 题意 翰翰和达达饲养了 N只小猫&#xff0c;这天&#xff0c;小猫们要去爬山。 经历了千辛万苦&#xff0c;小猫们终于爬上了山顶&#xff0c;但是疲倦的它们再也不想徒步走下山了&#xff08;呜咕…...

ECharts教程(详细)

ECharts教程(详细) 非常全面的ECharts教程&#xff0c;非常全面的ECharts教程&#xff0c;目前线条/节点颜色、线条粗细、线条样式、线条阴影、线条平滑、线条节点大小、线条节点阴影、线条节点边框、线条节点边框阴影、工具提醒、工具提醒样式、工具自定义提醒、工具提醒背景…...

pinia

目录一、介绍二、快速上手1.安装2.基本使用与state3.actions的使用4.getters的使用5.storeToRefs的使用6.pinia模块化三、数据持久化1.安装2.使用插件3.模块开启持久化4.按需缓存模块的数据一、介绍 pinia从使用角度和之前Vuex几乎是一样的&#xff0c;比Vuex更简单了。 在Vu…...

mysql中insert语句的五种用法

文章目录前言一、values参数后单行插入二、values参数后多行插入三、搭配select插入数据四、复制旧表的信息到新表五、搭配set插入数据总结前言 insert语句是标准sql中的语法&#xff0c;是插入数据的意思。在实际应用中&#xff0c;它也演变了很多种用法来实现特殊的功能&…...

YOLOV7模型调试记录

先前的YOLOv7模型是pytorch重构的&#xff0c;并非官方提供的源码&#xff0c;而在博主使用自己的数据集进行实验时发现效果并不理想&#xff0c;因此生怕是由于源码重构导致该问题&#xff0c;此外还需进行对比实验&#xff0c;因此便从官网上下载了源码&#xff0c;进行调试运…...

模拟光伏不确定性——拉丁超立方抽样生成及缩减场景(Matlab全代码)

光伏出力的不确定性主要源于预测误差,而研究表明预测误差(e)服从正态分布且大概为预测出力的10%。本代码采用拉丁超立方抽样实现场景生成[1,2]、基于概率距离的快速前代消除法实现场景缩减[3],以此模拟了光伏出力的不确定性。与风电不确定性模拟不同之处在于——光伏存在0出…...

Elasticsearch聚合查询速览

Es 数据分析工具 - Elasticsearch Aggregations &#xff08;聚合查询&#xff09; 官方文档 Aggregations | Elasticsearch Guide [7.15] | Elastic 1. Bucket aggregations 桶聚合 that group documents into buckets, also called bins, based on field values, ranges, o…...

CEC2017:鱼鹰优化算法(Osprey optimization algorithm,OOA)求解cec2017(提供MATLAB代码)

一、鱼鹰优化算法简介 鱼鹰优化算法&#xff08;Osprey optimization algorithm&#xff0c;OOA&#xff09;由Mohammad Dehghani 和 Pavel Trojovsk于2023年提出&#xff0c;其模拟鱼鹰的捕食行为。 鱼鹰是鹰形目、鹗科、鹗属的仅有的一种中型猛禽。雌雄相似。体长51-64厘米…...

Vue3 企业级项目实战:通关 Vue3 企业级项目开发,升职加薪快人一步

Vue3 企业级项目实战 - 程序员十三 - 掘金小册Vue3 Element Plus Spring Boot 企业级项目开发&#xff0c;升职加薪&#xff0c;快人一步。。「Vue3 企业级项目实战」由程序员十三撰写&#xff0c;2744人购买https://s.juejin.cn/ds/S2RkR9F/ 课程介绍 很高兴为大家介绍这个…...

vue样式绑定(v-if)

文章目录一.第一次用vue框架二.要求:1.定义两种样式&#xff0c;一种描述正确的状态&#xff0c;一种描述错误的状态。2.在结构代码中定义一个块&#xff0c;实现绑定正确的样式状态。3.定义一个按钮&#xff0c;实现正确和错误两种状态的class切换。三.源代码四.效果一.第一次…...

无需公网IP,安全稳定实现U8C异地访问

用友是全球领先的企业云服务与软件提供商&#xff0c;在财务、人力、供应链、采购、制造、营销、研发、项目、资产、协同等领域为客户提供数字化、智能化、社会化的企业云服务产品与解决方案。 U8C是用友针对成长型、创新型企业&#xff0c;提供企业级ERP整体解决方案。在系统…...

Graph Neural Network(GNN)图神经网络

Graph Neural Network(GNN)图神经网络&#xff0c;是一种旨在对图结构数据就行操作的深度学习算法。它可以很自然地表示现实世界中的很多问题&#xff0c;包括社交网络&#xff0c;分子结构和交通网络等。GNN旨在处理此类图结构数据&#xff0c;并对图中的节点和边进行预测或执…...

JSTL核心库的简单使用

JSTL核心库的简单使用 7.1考试重点 7.1.1c:out输出数据 考试重点就是c的相关的 jar包下载地址:Apache Tomcat - Apache Taglibs Downloads 看会典型应用就可以<% page contentType"text/html;charsetUTF-8" language"java" %> <% taglib uri"…...

ffmpeg.dll丢失怎么办,有什么修复ffmpeg.dll的方法

如果你在运行某些音视频软件或游戏时遇到了“ffmpeg.dll丢失”的错误消息&#xff0c;这意味着你的Windows系统中缺少了ffmpeg.dll文件&#xff0c;这是一个必要的动态链接库&#xff08;DLL&#xff09;文件&#xff0c;用于支持许多音视频软件和游戏的运行。在这篇文章中&…...

【学习笔记】NOIP爆零赛9

这场考炸了&#xff0c;不过也还好&#xff0c;正好给自己警醒的作用 t1t1t1应该是想到正解了&#xff0c;就是最后边界那个地方还是没有想清楚&#xff0c;哎这种交互题卡询问次数还是挺难受的&#xff0c;并且似乎我对于这种细节并不能很好把握。然后就少了50pts50pts50pts是…...

SpringMVC的常用组件和工作流程及部分注解解析

一丶SpringMVC常用的组件 1.前端控制器DispatcherServlet 作用&#xff1a;统一处理请求和响应。除此之外还是整个流程控制的中心&#xff0c;由 DispatcherServlet 来调用其他组件&#xff0c;处理用户的请求 接收请求&#xff0c;响应结果&#xff0c;相当于转发器&#xff…...

创建Firebase项目并接入Firebase推送: Firebase Cloud Messaging (FCM)

1.FCM简介&#xff1a;Firebase Cloud Messaging (FCM) 是一种跨平台消息传递解决方案&#xff0c;可供您可靠地传递消息&#xff0c;而且还是免费的服务。支持 Android&#xff0c;IOS,Web,Flutter,Unity.消息类型可以使用 FCM 向客户端发送两种类型的消息&#xff1a;通知消息…...

MyBatis的简单使用

MyBatis是一个优秀的持久型框架用于简化JDBC开发&#xff0c;JDBC的原生写法普遍都很麻烦&#xff0c;还要写原汁原味的sql语句&#xff0c;mybatis将很多东西都放到了配置文件里面然后用少量代码简化了免除了几乎所有的JDBC代码以及设定参数和获取结果集的工作。MyBatis 可以通…...

最新的Windows docker安装方法

什么是Docker&#xff1f;关于Docker的相关概述&#xff0c;请看&#xff1a;Docker_面向架构编程的博客-CSDN博客在Windows10 or Windows11中安装docker主要就两步&#xff1a;1.安装wsl22. 安装docker一、安装WSL2安装wslwsl --install然后重启一下电脑在cmd窗口可以查看自己…...

2023软件测试工程师涨薪攻略,3年如何达到30K

1.软件测试如何实现涨薪 首先涨薪并不是从8000涨到9000这种涨薪&#xff0c;而是从8000涨到15K加到25K的涨薪。基本上三年之内就可以实现。 如果我们只是普通的有应届毕业生或者是普通本科那我们就只能从小公司开始慢慢往上走。 有些同学想去做测试&#xff0c;是希望能够日…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...

TI德州仪器TPS3103K33DBVR低功耗电压监控器IC电源管理芯片详细解析

1. 基本介绍 TPS3103K33DBVR 是 德州仪器&#xff08;Texas Instruments, TI&#xff09; 推出的一款 低功耗电压监控器&#xff08;Supervisor IC&#xff09;&#xff0c;属于 电源管理芯片&#xff08;PMIC&#xff09; 类别&#xff0c;主要用于 系统复位和电压监测。 2. …...