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

UVa 307 Sticks 木棍拼接 ID 迭代加深搜

题目链接:Sticks
题目描述:

小明一开始有一些长度相等的木棍,小明现在将木棍砍成了一些长度为整数的木棍,他现在忘记了最开始木棍的长度,你需要找到最短的可能木棍长度,例如给定5,2,1,5,2,1,5,2,15,2,1,5,2,1,5,2,15,2,1,5,2,1,5,2,1那么这些木棍可以是由一根长度为242424的木棍砍出来的,但是也可以是两根长度为121212的木棍砍出来,也可以是三根长度为888的木棍看出,也可以是444根长度为666的木棍砍出来。其中666是长度最短的,你需要输出666

题解:

由于本题的初始有几根木棍我们并不确定,我们实际上可以倒序枚举初始的木棍数量(从nnn开始,因为初始木棍的数量越多,木棍的长度也短),然后依次搜索所有情况,这就是一个倒序的IDIDID算法(通常IDIDID都是正着枚举)。
本题的难点在于如何进行搜索。枚举了初始的木棍数量之后,我们就知道了初始的每一根木棍的长度,也就是木棍的长度和除以初始木棍的数量,我们可以将木棍的长度进行排序,我们每次选择木棍进行组合的时候,我们优先处理长度更长的木棍,尝试将其拼接在当前的木棍上,如果长度大于了初始木棍的长度我们可以继续选择稍小的木棍进行处理,如果刚好等于初始木棍的长度,那么我们一定是选择其与当前的木棍进行组合,而不是选择几根更短的木棍进行组合,这是因为如果选择几根更短的木棍,那么剩余木棍的灵活性就会降低,而我们选择这一根木棍进行组合,剩下的木棍有着更多的组合可能性,这也就表明了如果选择一根进行拼接刚好等于初始长度的时候,如果搜索失败即使选择更短的木棍也会搜索失败。

代码:

#include <bits/stdc++.h>using namespace std;int n, maxDepth, sum;
vector<int> len;
bool *used;bool dfs(int nowDepth, int nowLen, int pos)
{if (nowDepth == maxDepth) { return true; }for (int i = pos; i >= 0; i--) {if (used[i]) { continue; }if (nowLen + len[i] < sum / maxDepth) {used[i] = true;if (dfs(nowDepth, nowLen + len[i], i - 1)) { return true; }used[i] = false;while (i - 1 >= 0 && len[i - 1] == len[i]) { i--; } // 相同长度此时一定会失败} else if (nowLen + len[i] == sum / maxDepth) {used[i] = true;if (dfs(nowDepth + 1, 0, n - 1)) { return true; }used[i] = false;return false; // 没有必要选择更短的,因为灵活性更低了}if (nowLen == 0) { return false; } // 这里是为了防止重复搜索}return false;
}int main()
{while (cin >> n && n != 0) {len.resize(n);used = new bool[n]; // 这题没有告知数据范围,所以这里采用了动态内存分配sum = 0;for (int i = 0; i < n; i++) {cin >> len[i];sum += len[i];}sort(len.begin(), len.end());for (maxDepth = n; ;maxDepth--) {if (sum % maxDepth != 0 || len[n - 1] > sum / maxDepth) { continue; }memset(used, 0, sizeof(bool) * n);if (dfs(0, 0, n - 1)) { break; }}cout << sum / maxDepth << endl;delete used;}return 0;
}

相关文章:

UVa 307 Sticks 木棍拼接 ID 迭代加深搜

题目链接&#xff1a;Sticks 题目描述&#xff1a; 小明一开始有一些长度相等的木棍&#xff0c;小明现在将木棍砍成了一些长度为整数的木棍&#xff0c;他现在忘记了最开始木棍的长度&#xff0c;你需要找到最短的可能木棍长度&#xff0c;例如给定5,2,1,5,2,1,5,2,15,2,1,5,2…...

阿里云(CentOS)中MySQL8忘记密码的解决方法

阿里云(CentOS)中MySQL8忘记密码的解决方法 方法 在 skip-grant-tables 模式下启动 MySQL&#xff0c;该模式下启动 MySQL 时不启动授权表功能&#xff0c;可以直接免密码登录 实现 编辑 /etc/my.cnf 文件 vim /etc/my.cnf在 [mysqld] 区域末尾添加配置&#xff0c;设置免密…...

三、Spring的入门程序

第一个Spring程序 创建新的空工程spring6 设置JDK版本17&#xff0c;编译器版本17 设置IDEA的Maven&#xff1a;关联自己的maven 在空的工程spring6中创建第一个maven模块&#xff1a;spring6-001-first 在pom.xml添加spring context依赖和junit依赖&#xff0c; <?x…...

摘录一下Python列表和元组的学习笔记

1 基础概念 列表一个值&#xff0c;列表值指的是列表本身&#xff0c;而不是列表中的内容 列表用[]表示 列表中的内容称为 表项 len()函数可以显示列表中表项的个数&#xff0c;比如下面这个例子 spam [cat, bat, dog, rat]print(len(spam))列表的范围选取中&#xff0c;比…...

【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤

【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤 1 收益率 在学术界&#xff0c;建模一般不直接使用资产价格&#xff0c;而是使用资产收益率(Returns)。因为收益率比价格具有更好的统计特性&#xff0c;更便于建模。下经典…...

1_机器学习概述—全流程

文章目录1 机器学习定义2 机器学习常见应用框架&#xff08;重点&#xff09;3 机器学习分类3.1 监督学习&#xff08;Supervised learning&#xff09;3.2 无监督学习&#xff08;Unsupervised learning&#xff09;3.3 半监督学习&#xff08;Semi-Supervised Learning&#…...

VUE中给对象添加新属性时,界面不刷新怎么办

一、直接添加属性的问题 举例&#xff1a; 定义一个p标签&#xff0c;通过v-for指令进行遍历 然后给botton标签绑定点击事件&#xff0c;我们预期点击按钮时&#xff0c;数据新增一个属性&#xff0c;界面也 新增一行。 <p v-for"(value,key) in item" :key&qu…...

视频号频出10w+,近期爆红的账号有哪些?

回顾2月&#xff0c;视频号持续放出大动作&#xff0c;不仅进行了16小时不间断的NBA全明星直播&#xff0c;还邀请国际奥委会入驻&#xff0c;分享奥运的最新资讯。视频号成为越来越多官方机构宣传推广的有效渠道。官方积极入驻&#xff0c;内容创作生态也在同步繁荣发展&#…...

企业寄件现代化管理教程

现代化企业为了跟上时代发展的步伐&#xff0c;在不断完善着管理制度&#xff0c;其中公司寄件管理&#xff0c;也是重要的一个模块。为了提高公司快递的寄件效率&#xff0c;以及节约寄件成本&#xff0c;实现快递寄件的规范化&#xff0c;越来越多的现代化企业&#xff0c;开…...

django 在网页显示后台进度

1、定义函数打开网页 def PeformanceIndex(request): citys{‘wuhu’: ‘芜湖’, ‘xuancheng’: ‘宣城’, ‘tongling’: ‘铜陵’, ‘suzhou’: ‘宿州’, ‘maanshan’: ‘马鞍山’, ‘liuan’: ‘六安’, ‘huainan’: ‘淮南’, ‘huabei’: ‘淮北’, ‘hefei’: ‘合肥…...

机器学习库(Numpy, Scikit-learn)

Numpy 创建数组 import numpy as npa np.array([1,2,3]) b np.array([(1.5,2,3), (4,5,6)], dtype float) c np.array([[(1.5,2,3), (4,5,6)], [(3,2,1), (4,5,6)]],dtype float)创建占位符 z1np.zeros((3,4)) z2np.ones((2,3,4),dtypenp.int16) z3d np.arange(10,25,5)…...

Linux操作系统学习(进程替换)

文章目录进程替换进程替换是什么&#xff1f;替换的方法进程替换简易shell模拟进程替换 进程替换是什么&#xff1f; 如下图所示&#xff1a; ​ 进程替换就是&#xff0c;把进程B的代码和数据&#xff0c;替换正在执行的进程A的代码和数据在内存中的位置&#xff08;若代码…...

【C++从入门到放弃】类和对象(中)———类的六大默认成员函数

&#x1f9d1;‍&#x1f4bb;作者&#xff1a; 情话0.0 &#x1f4dd;专栏&#xff1a;《C从入门到放弃》 &#x1f466;个人简介&#xff1a;一名双非编程菜鸟&#xff0c;在这里分享自己的编程学习笔记&#xff0c;欢迎大家的指正与点赞&#xff0c;谢谢&#xff01; 类和对…...

白盒测试重点复习内容

白盒测试白盒测试之逻辑覆盖法逻辑覆盖用例设计方法1.语句覆盖2.判定覆盖(分支覆盖)3.条件覆盖4.判定条件覆盖5.条件组合覆盖6.路径覆盖白盒测试之基本路径测试法基本路径测试方法的步骤1.根据程序流程图画控制流图2.计算圈复杂度3.导出测试用例4.准备测试用例5.例题白盒测试总…...

【13】linux命令每日分享——groupadd建立组

大家好&#xff0c;这里是sdust-vrlab&#xff0c;Linux是一种免费使用和自由传播的类UNIX操作系统&#xff0c;Linux的基本思想有两点&#xff1a;一切都是文件&#xff1b;每个文件都有确定的用途&#xff1b;linux涉及到IT行业的方方面面&#xff0c;在我们日常的学习中&…...

《第一行代码》 第十章:服务

一&#xff0c;在子线程中更新UI 1&#xff0c;新建项目&#xff0c;修改布局代码 <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"&g…...

简单介绍编程进制

十进制 十进制的位权为 10&#xff0c;比如十进制的 123&#xff0c;123 1 * 10 ^ 2 2 * 10 ^ 1 3 * 10 ^ 0。 二进制 二进制的位权为 2&#xff0c;比如十进制的 4&#xff0c;二进制为 100&#xff0c;4 1 * 2 ^ 2 0 * 2 ^ 1 0 *2 ^ 0。 Java7 之前&#xff0c;不支…...

windows忘记开机密码怎么办

windows忘记开机密码怎么办 清除windows登录密码 清除windows登录密码简单方法 开机到欢迎界面时&#xff0c;按CtrlAltDelete两次&#xff0c;跳出帐号窗口&#xff0c;输入用户名&#xff1a;administrator&#xff0c;回车&#xff0c; 或者启动时按F8 选“带命令行的安全…...

SpringCloud:Eureka

目录 一、eureka的作用 二、搭建Eureka服务端 三、添加客户端 四、服务发现 提供者与消费者 服务提供者&#xff1a;一次业务中&#xff0c;被其它微服务调用的服务。&#xff08;提供接口给其它微服务) 服务消费者&#xff1a;一次业务中&#xff0c;调用其它微服务的服…...

如何获取或设置CANoe以太网网卡信息(SET篇)

CAPL提供了一系列函数用来操作CANoe网卡。但是,但是,首先需要明确一点,不管是获取网卡信息,还是设置网卡信息,只能访问CAPL程序所在的节点下的网卡,而不是节点所在的以太网通道下的所有网卡 关于第一张图中,Class节点下,有三个网卡:Ethernet1、VLAN 1.100、VLAN 1.200…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...