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 迭代加深搜
题目链接:Sticks 题目描述: 小明一开始有一些长度相等的木棍,小明现在将木棍砍成了一些长度为整数的木棍,他现在忘记了最开始木棍的长度,你需要找到最短的可能木棍长度,例如给定5,2,1,5,2,1,5,2,15,2,1,5,2…...
 
阿里云(CentOS)中MySQL8忘记密码的解决方法
阿里云(CentOS)中MySQL8忘记密码的解决方法 方法 在 skip-grant-tables 模式下启动 MySQL,该模式下启动 MySQL 时不启动授权表功能,可以直接免密码登录 实现 编辑 /etc/my.cnf 文件 vim /etc/my.cnf在 [mysqld] 区域末尾添加配置,设置免密…...
 
三、Spring的入门程序
第一个Spring程序 创建新的空工程spring6 设置JDK版本17,编译器版本17 设置IDEA的Maven:关联自己的maven 在空的工程spring6中创建第一个maven模块:spring6-001-first 在pom.xml添加spring context依赖和junit依赖, <?x…...
 
摘录一下Python列表和元组的学习笔记
1 基础概念 列表一个值,列表值指的是列表本身,而不是列表中的内容 列表用[]表示 列表中的内容称为 表项 len()函数可以显示列表中表项的个数,比如下面这个例子 spam [cat, bat, dog, rat]print(len(spam))列表的范围选取中,比…...
【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤
【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤 1 收益率 在学术界,建模一般不直接使用资产价格,而是使用资产收益率(Returns)。因为收益率比价格具有更好的统计特性,更便于建模。下经典…...
 
1_机器学习概述—全流程
文章目录1 机器学习定义2 机器学习常见应用框架(重点)3 机器学习分类3.1 监督学习(Supervised learning)3.2 无监督学习(Unsupervised learning)3.3 半监督学习(Semi-Supervised Learning&#…...
 
VUE中给对象添加新属性时,界面不刷新怎么办
一、直接添加属性的问题 举例: 定义一个p标签,通过v-for指令进行遍历 然后给botton标签绑定点击事件,我们预期点击按钮时,数据新增一个属性,界面也 新增一行。 <p v-for"(value,key) in item" :key&qu…...
 
视频号频出10w+,近期爆红的账号有哪些?
回顾2月,视频号持续放出大动作,不仅进行了16小时不间断的NBA全明星直播,还邀请国际奥委会入驻,分享奥运的最新资讯。视频号成为越来越多官方机构宣传推广的有效渠道。官方积极入驻,内容创作生态也在同步繁荣发展&#…...
 
企业寄件现代化管理教程
现代化企业为了跟上时代发展的步伐,在不断完善着管理制度,其中公司寄件管理,也是重要的一个模块。为了提高公司快递的寄件效率,以及节约寄件成本,实现快递寄件的规范化,越来越多的现代化企业,开…...
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操作系统学习(进程替换)
文章目录进程替换进程替换是什么?替换的方法进程替换简易shell模拟进程替换 进程替换是什么? 如下图所示:  进程替换就是,把进程B的代码和数据,替换正在执行的进程A的代码和数据在内存中的位置(若代码…...
 
【C++从入门到放弃】类和对象(中)———类的六大默认成员函数
🧑💻作者: 情话0.0 📝专栏:《C从入门到放弃》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢! 类和对…...
 
白盒测试重点复习内容
白盒测试白盒测试之逻辑覆盖法逻辑覆盖用例设计方法1.语句覆盖2.判定覆盖(分支覆盖)3.条件覆盖4.判定条件覆盖5.条件组合覆盖6.路径覆盖白盒测试之基本路径测试法基本路径测试方法的步骤1.根据程序流程图画控制流图2.计算圈复杂度3.导出测试用例4.准备测试用例5.例题白盒测试总…...
 
【13】linux命令每日分享——groupadd建立组
大家好,这里是sdust-vrlab,Linux是一种免费使用和自由传播的类UNIX操作系统,Linux的基本思想有两点:一切都是文件;每个文件都有确定的用途;linux涉及到IT行业的方方面面,在我们日常的学习中&…...
 
《第一行代码》 第十章:服务
一,在子线程中更新UI 1,新建项目,修改布局代码 <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"&g…...
 
简单介绍编程进制
十进制 十进制的位权为 10,比如十进制的 123,123 1 * 10 ^ 2 2 * 10 ^ 1 3 * 10 ^ 0。 二进制 二进制的位权为 2,比如十进制的 4,二进制为 100,4 1 * 2 ^ 2 0 * 2 ^ 1 0 *2 ^ 0。 Java7 之前,不支…...
windows忘记开机密码怎么办
windows忘记开机密码怎么办 清除windows登录密码 清除windows登录密码简单方法 开机到欢迎界面时,按CtrlAltDelete两次,跳出帐号窗口,输入用户名:administrator,回车, 或者启动时按F8 选“带命令行的安全…...
 
SpringCloud:Eureka
目录 一、eureka的作用 二、搭建Eureka服务端 三、添加客户端 四、服务发现 提供者与消费者 服务提供者:一次业务中,被其它微服务调用的服务。(提供接口给其它微服务) 服务消费者:一次业务中,调用其它微服务的服…...
 
如何获取或设置CANoe以太网网卡信息(SET篇)
CAPL提供了一系列函数用来操作CANoe网卡。但是,但是,首先需要明确一点,不管是获取网卡信息,还是设置网卡信息,只能访问CAPL程序所在的节点下的网卡,而不是节点所在的以太网通道下的所有网卡 关于第一张图中,Class节点下,有三个网卡:Ethernet1、VLAN 1.100、VLAN 1.200…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
 
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
 
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
 
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
 
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
 
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
