167. 木棒(dfs剪枝,经典题)
167. 木棒 - AcWing题库
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据,每组数据包括两行。
第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。
第二行是截断以后,所得到的各节木棍的长度。
在最后一组数据之后,是一个零。
输出格式
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于 50。
输入样例:
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例:
6
5
解析:
本题是一道经典的dfs剪枝题,主要有三种剪枝:
剪枝 1:sum % length == 0 只有 length是 sum的约数才有可能凑出多个等长的木棒
剪枝 2:优化搜索顺序,木棍长度从大到小排序,可以减少搜索的分支
排除等效冗余优化:
剪枝 3-1:确定每根木棒中木棍的枚举顺序,因为我们的方案和顺序没有关系,以组合的形 式枚举方案可以少搜很多重复方案
剪枝 3-2:如果当前木棍没有搜到方案,则跳过所有长度相等的木棍
剪枝 3-3:如果是木棒的第一根木棍就搜索失败了,则一定搜不到方案
剪枝 3-4:如果是木棒的最后一根木棍(+ 上它木棒长度正好是 length)搜索失败了,也一 定搜不到方案
可以想想怎么证明上述几种剪枝的正确性,dfs和动态规划很像
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
const int N = 70;
int n;
int ar[N],vis[N], len, sum;int cmp(const int& a, const int& b) {return a > b;
}bool dfs(int u, int s,int start) {/*cout << "KKKKKKKKKKKKKKKKK "<<len<<" "<<s << endl;for (int i = 1; i <= n; i++) {cout << vis[i] << " ";}cout << endl << endl;*/if (u * len == sum) {/*cout << "_______________" << u << endl;*/return 1;}if (s == len) {return dfs(u + 1, 0, 0);/*if (dfs(u + 1, 0, 0)) {cout << "LLLLLLLLLLLLL " << 1 << endl;return 1;}*/}for (int i = start; i <= n; i++) {if (vis[i])continue;if (s + ar[i] > len)continue;vis[i] = 1;if (dfs(u, s + ar[i], i + 1))return 1;vis[i] = 0;if (s == 0 || s + ar[i] == len)return 0;int j = i;while (j <= n && ar[j] == ar[i])j++;i = j - 1;}return 0;
}int main() {while (cin >> n, n) {int mx = 0;sum = 0;for (int i = 1; i <= n; i++) {scanf("%d", &ar[i]);sum += ar[i];mx = max(mx, ar[i]);}memset(vis, 0, sizeof vis);sort(ar + 1, ar + 1 + n, cmp);len = mx;while (1) {while (sum % len != 0)len++;//cout << "++++++"<<len << endl;if (dfs(0, 0, 1)) {printf("%d\n", len);break;}len++;}}return 0;
}
相关文章:
167. 木棒(dfs剪枝,经典题)
167. 木棒 - AcWing题库 乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。 请你设计一个程序࿰…...
用HTML的原生语法实现两个div子元素在同一行中排列
代码如下: <div id"level1" style"display: flex;"><div id"level2-1" style"display: inline-block; padding: 10px; border: 1px solid #ccc; margin: 5px;">这是第一个元素。</div><div id"…...
C++进阶--map和set的介绍及使用
map和set的介绍及使用 一、关联式容器与键值对关联式容器键值对pair树形结构的关联式容器 二、set2.1 set的介绍2.2 set的使用2.2.1 set的模板参数列表2.2.2 set的构造2.2.3 set的迭代器2.2.4 set的容量2.2.5 set修改操作2.2.6 set的使用举例 三、multiset3.1 multiset的介绍3.…...
MIML-DA
图3呢?且作者未提供代码...
[ROS2 Foxy]#1.3 安装使用 turtlesim
官网教程: https://docs.ros.org/en/foxy/Tutorials/Turtlesim/Introducing-Turtlesim.html 1.turtlesim安装和使用 turtlesim是一个轻量级的模拟程序,用来学习ROS2 .通过turtlesim来介绍ROS2在一个基础的水平上都要做了那些事,以此让我们了解将来在真的 robot或者模拟器上使用…...
嵌入式培训机构四个月实训课程笔记(完整版)-Linux系统编程第三天-Linux进程(物联技术666)
更多配套资料CSDN地址:点赞+关注,功德无量。更多配套资料,欢迎私信。 物联技术666_嵌入式C语言开发,嵌入式硬件,嵌入式培训笔记-CSDN博客物联技术666擅长嵌入式C语言开发,嵌入式硬件,嵌入式培训笔记,等方面的知识,物联技术666关注机器学习,arm开发,物联网,嵌入式硬件,单片机…...
1-01初识C语言
一、概述 C语言是贝尔实验室的Ken Thompson(肯汤普逊)、Dennis Ritchie(丹尼斯里奇)等人开发的UNIX 操作系统的“副产品”,诞生于1970年代初。 Thompson和Ritchie共同创作完成了Unix操作系统,他们都被称为…...
Python字符串
定义字符串 Python中要定义一个字符串,有比较多的一种方式。 示例代码: s "你好,张大鹏" print(s, type(s))s 你好,张大鹏 print(s, type(s))s """你好,张大鹏""" prin…...
PHP 基础编程 1
文章目录 前后端交互尝试php简介php版本php 基础语法php的变量前后端交互 - 计算器体验php数据类型php的常量和变量的区别php的运算符算数运算符自增自减比较运算符赋值运算符逻辑运算 php的控制结构ifelseelse if 前后端交互尝试 前端编程语言:JS (Java…...
Android studio BottomNavigationView 应用设计
一、新建Bottom Navigation Activity项目: 二、修改bottom_nav_menu.xml: <itemandroid:id="@+id/navigation_beijing"android:icon="@drawable/ic_beijing_24dp"android:title="@string/title_beijing" /><itemandroid:id="@+i…...
51单片机串行口相关知识
51单片机串行口相关知识 串行通信概念 计算机与外部通信方式就两种: 并行通信串行通信 两种通信方式的特点以及适用场景: 名称特点适用场景并行通信速度快,效率高,成本高适合短距离高速通信,如计算机内部各硬件之…...
IDEA 每次新建工程都要重新配置 Maven的解决方案
文章目录 IDEA 每次新建工程都要重新配置 Maven 解决方案一、选择 File -> New Projects Setup -> Settingsfor New Projects…二、选择 Build,Execution,Deployment -> Build Tools -> Maven IDEA 每次新建工程都要重新配置 Maven 解决方案 DEA 每次新建工程都要…...
SecOC中新鲜度值和MAC都按照完整的值来生成,但是在发送和认证的时候只会截取一部分。这边截取的部分一般取多长?由什么参数设定?
新鲜度值(Freshness Value, FV)和消息验证码(Message Authentication Code, MAC)是SecOC协议中用于保证数据的真实性和新鲜度的重要信息。它们的长度取决于不同的因素,如加密算法、安全级别、通信带宽等。 一般来说,FV和MAC的长度越长,安全性越高,但也会占用更多的通信…...
信源编码与信道转移矩阵
目录 一. 信息论模型 二. 点对点通信模型 三. 信源编码 四. 信道转移矩阵 4.1 二进制对称信道 4.2 二进制擦除信道 五. 小结 (1)信道直射与反射 (2)信道散射 (3) 信道时变性 一. 信息论模型 194…...
React 实现拖放功能
介绍 本篇文章将会使用react实现简单拖放功能。 样例 布局侧边栏拖放 LayoutResize.js import React, {useState} from "react"; import { Button } from "antd"; import "./LayoutResize.css";export const LayoutResize () > {const […...
马克思主义基本原理笔记
马克思主义哲学、政治经济学、科学社会主义理论 哲学 马克思主义中国化的理论成果:毛泽东思想、邓小平理论、三个代表重要思想、科学发展观 物质和意识哪个是本原,是哲学的基本问题 辩证法认为世界上的事物都是相互联系的、运动发展的,形…...
Vue+JavaSpingBoot笔记(1)
一、前后端通信参数问题 1.集合【字典】类型 Vue前端传递参数: export default {methods: { test(){// 将 filteredData 中的每一行值放入 newData 对象数组中 const newData filteredData.map(item > ({key1: item.Value1,key2: item.Value2,key3: "测试"}));r…...
10-单例模式(Singleton)
意图 保证一个类只有一个实例,并提供一个访问它的全局访问点 实现 1 懒汉式,线程不安全 public class Singleton { private static Singleton instance; private Singleton (){} public static Singleton getInstance() { if (instance null) {…...
C++ 求一个数是否是丑数。
#include<string.h> #include <iostream> using namespace std; int isChou(int num) { if (num < 0) { return 0; } while (num % 2 0) { // 不断除以2,直到不能整除为止 num / 2; } while (num % 3 0) { // 不断除…...
SpringCloud系列篇:核心组件之注册中心组件
🥳🥳Welcome Huihuis Code World ! !🥳🥳 接下来看看由辉辉所写的关于SpringCloud的相关操作吧 目录 🥳🥳Welcome Huihuis Code World ! !🥳🥳 一.注册中心组件是什么 二.注册中心…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
QT开发技术【ffmpeg + QAudioOutput】音乐播放器
一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下,音视频内容犹如璀璨繁星,点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频,到在线课堂中知识渊博的专家授课,再到影视平台上扣人心弦的高清大片,音…...
