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 ! !🥳🥳 一.注册中心组件是什么 二.注册中心…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
