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 ! !🥳🥳 一.注册中心组件是什么 二.注册中心…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
