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

P1120 小木棍(搜索+剪枝)

题目链接:P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

样例输入: 

9
5 2 1 5 2 1 5 2 1

样例输出:

6

分析:这道题一看数据范围就知道是搜索,但关键是需要剪枝。

首先我们求出所有木棍的长度和,那么原始木棍的长度一定是长度和的因子,这是显然的,然后我们就开始对每个因子进行从小到大搜索。

根据贪心性质我们可以知道优先选用长的木棍进行组装,因为短的木棍在任何情况下都可以替换等长的长的木棍,但是长的木棍在有些情况下无法替换短的木棍,所以我们首先要对木棍进行从大到小排序。

先来看一下搜索函数的参数,假如我们要枚举的长度是len,首先需要知道当前长度为len的木棍还差多少,也就是res,然后还需要知道组成当前木棍的上一节子棍的长度last,因为我们枚举的子棍是逐渐减少的,所以这个可以用于剪枝,最后一个就是当前我们还差几根长度为len的木棍就可以完整拼完了。

下面来分析一下哪些地方可以剪枝:

1.如果我们一开始拼一节长度为len的木棍,这个时候还没有放上去小木棍,那么这个时候我们就放上去还未使用过的长度最长的木棍。因为所有木棍最后都一定要用上的

2.我们可以用nx[i]标记下一个与第i根木棍长度不一致的编号,假如我们当前用第i根木棍没有拼接成功,那么如果下一根木棍跟当前木棍长度一样,那么我们也就没有必要用下一根木棍了,直接选用下一个跟当前木棍长度不一致的木棍即可

3.我们记录了组装当前木棍的剩余长度res和组成当前木棍的上一个子木棍last,那么我们下一根木棍的长度一定是小于等于两者的较小值的,查询第一个小于等于两者较小值的木棍我们可以用二分来查找

4.根据第一条剪枝我们可以知道,假如当前木棍还没有开始拼,我们优先选择未使用过且最长的木棍来进行拼接,但是如果拼接失败,那么我们没必要用更小的木棍去尝试拼接,直接返回false即可,如果要是剩余的长度等于当前木棍的长度而且还未拼接成功这就代表着我们在组装当前木棍时选取最合适子木棍依旧无法拼接成功,那么这个时候我们也是直接返回false即可。

加上上面四个剪枝就可以ac了

细节见代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=100;
int a[N],len;
bool vis[N];
int nx[N];
bool cmp(int a,int b)
{return a>b;
}
int n;
bool dfs(int res,int last,int cnt)//res记录当前这根木棍还剩的拼接长度,last记录拼接当前木棍的上一个木棍的长度,cnt记录还剩多少个木棍 
{if(res==0){if(cnt==1) return true;for(int i=2;i<=n;i++)//选择第一个没有被使用的木棍进行拼接 {if(vis[i]) continue;vis[i]=true;if(dfs(len-a[i],a[i],cnt-1)) return true;vis[i]=false;break;}}int l=1,r=n;int t=min(last,res);while(l<r)//二分找第一个可以填的位置,下一个子棍的长度一定小于等于上一根拼接该木棍的子棍长度 {int mid=l+r>>1;if(a[mid]<=t) r=mid;else l=mid+1;}	for(int i=l;i<=n;i++){if(vis[i]) continue;vis[i]=true;bool flag=dfs(res-a[i],a[i],cnt);vis[i]=false;if(flag) return true;//有一个可以了就可以退出了 if(res==a[i]||res==len) return false; i=nx[i]-1;//用第i根木棍没有拼接成功 }return false; 
}
int main()
{cin>>n;int sum=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}sort(a+1,a+n+1,cmp);nx[n]=n+1;for(int i=n-1;i>=1;i--){if(a[i]==a[i+1]) nx[i]=nx[i+1];else nx[i]=i+1;}int ans=sum;for(len=a[1];len<=sum/2;len++)//枚举原始木棍长度{if(sum%len) continue;vis[1]=true;if(dfs(len-a[1],a[1],sum/len)){ans=len;break;}}printf("%d",ans);return 0;
}

相关文章:

P1120 小木棍(搜索+剪枝)

题目链接&#xff1a;P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入&#xff1a; 9 5 2 1 5 2 1 5 2 1 样例输出&#xff1a; 6 分析&#xff1a;这道题一看数据范围就知道是搜索&#xff0c;但关键是需要剪枝。 首先我们求出所有木棍的长度和&am…...

【专项训练】动态规划-3

动态规划:状态转移方程、找重复性和最优子结构 分治 + 记忆化搜索,可以过度到动态规划(动态递推) function DP():# DP状态定义# 需要经验,需把现实问题定义为一个数组,一维、二维、三维……dp =[][] # 二维情况for i = 0...M:...

【Linux】信号+再谈进程地址空间

目录 一、Linux中的信号 1、Linux中的信号 2、进程对信号的处理 3、信号的释义 二、信号的捕捉 1、信号的捕捉signal() 2、信号的捕捉sigaction() 三、信号如何产生&#xff1f; 1、kill()用户调用kill向操作系统发送信号 通过命令行参数模仿写一个kill命令 2、rais…...

C++回顾(二十一)—— list容器

21.1 list概述 list是一个双向链表容器&#xff0c;可高效地进行插入删除元素。list不可以随机存取元素&#xff0c;所以不支持at.(pos)函数与[]操作符。It(ok) it5(err)需要添加头文件&#xff1a;#include <list> 21.2 list构造 &#xff08;1&#xff09;默认构造…...

爱国者一体机电脑蓝屏怎么U盘重装系统教学?

爱国者一体机电脑蓝屏怎么U盘重装系统教学&#xff1f;有用户使用的爱国者一体机电脑开机了之后突然变成了蓝屏的了。而且无法继续使用了&#xff0c;那么遇到这样的蓝屏问题怎么去进行系统的重装呢&#xff1f;一起来看看以下的U盘重装系统教学吧。 准备工作&#xff1a; 1、U…...

Vue学习笔记(9)

9.1 axios 9.1.1 概述 Axios是一个流行的基于Promise的HTTP客户端&#xff0c;用于在浏览器和Node中发送HTTP请求。它可以用于处理各种请求类型&#xff0c;例如GET&#xff0c;POST等。Axios可以很容易地与现代前端框架和库集成&#xff0c;例如React&#xff0c;Vue等。 A…...

中值滤波+Matlab仿真+频域响应分析

中值滤波 文章目录中值滤波理解中值滤波的过程Matlab 实现实际应用频域分析中值滤波是一种滤波算法&#xff0c;其目的是去除信号中的噪声&#xff0c;而不会对信号本身造成太大的影响。它的原理非常简单&#xff1a;对于一个给定的窗口大小&#xff0c;将窗口内的数值排序&…...

自然语言处理中数据增强(Data Augmentation)技术最全盘点

与“计算机视觉”中使用图像数据增强的标准做法不同&#xff0c;在NLP中&#xff0c;文本数据的增强非常少见。这是因为对图像的琐碎操作&#xff08;例如将图像旋转几度或将其转换为灰度&#xff09;不会改变其语义。语义上不变的转换的存在是使增强成为Computer Vision研究中…...

PINN解偏微分方程实例1

PINN解偏微分方程实例11. PINN简介2. 偏微分方程实例3. 基于pytorch实现代码4. 数值解参考资料1. PINN简介 PINN是一种利用神经网络求解偏微分方程的方法&#xff0c;其计算流程图如下图所示&#xff0c;这里以偏微分方程(1)为例。 ∂u∂tu∂u∂xv∂2u∂x2\begin{align} \frac{…...

【python 基础篇 十二】python的函数-------函数生成器

目录1.生成器基本概念2.生成器的创建方式3.生成器的输出方式4.send()方法5.关闭生成器6.注意事项1.生成器基本概念 是一个特色的迭代器&#xff08;迭代器的抽象层级更高&#xff09;所以拥有迭代器的特性 惰性计算数据 节省内存 ----就是不是立马生成所有数据&#xff0c;而是…...

elasticsearch全解 (待续)

目录elasticsearchELK技术栈Lucene与Elasticsearch关系为什么不是其他搜索技术&#xff1f;Elasticsearch核心概念Cluster&#xff1a;集群Node&#xff1a;节点Shard&#xff1a;分片Replia&#xff1a;副本全文检索倒排索引正向和倒排es的一些概念文档和字段索引和映射mysql与…...

springboot2集成knife4j

springboot2集成knife4j springboot2集成knife4j 环境说明集成knife4j 第一步&#xff1a;引入依赖第二步&#xff1a;编写配置类第三步&#xff1a;测试一下 第一小步&#xff1a;编写controller第二小步&#xff1a;启动项目&#xff0c;访问api文档 相关资料 环境说明 …...

Qt 性能优化:CPU占有率高的现象和解决办法

一、前言 在最近的项目中&#xff0c;发现执行 Qt 程序时&#xff0c;有些情况下的 CPU 占用率奇高&#xff0c;最高高达 100%。项目跑在嵌入式板子上&#xff0c;最开始使用 EGLFS 插件&#xff0c;但是由于板子没有单独的鼠标层&#xff0c;导致鼠标移动起来卡顿&#xff0c…...

MySQL专题(学会就毕业)

MySQL专题0.准备sql设计一张员工信息表&#xff0c;要求如下&#xff1a;编号&#xff08;纯数字&#xff09;员工工号 (字符串类型&#xff0c;长度不超过10位)员工姓名&#xff08;字符串类型&#xff0c;长度不超过10位&#xff09;性别&#xff08;男/女&#xff0c;存储一…...

Java高级技术:单元测试、反射、注解

目录 单元测试 单元测试概述 单元测试快速入门 单元测试常用注解 反射 反射概述 反射获取类对象 反射获取构造器对象 反射获取成员变量对象 反射获取方法对象 反射的作用-绕过编译阶段为集合添加数据 反射的作用-通用框架的底层原理 注解 注解概述 自定义注解 …...

C语言初识

#include <stdio.h>//这种写法是过时的写法 void main() {}//int是整型的意思 //main前面的int表示main函数调用后返回一个整型值 int main() {return 0; }int main() { //主函数--程序的入口--main函数有且仅有一个//在这里完成任务//在屏幕伤输出hello world//函数-pri…...

Cadence Allegro 导出Etch Length by Layer Report报告详解

⏪《上一篇》   🏡《上级目录》   ⏩《下一篇》 目录 1,概述2,Etch Length by Layer Report作用3,Etch Length by Layer Report示例4,Etch Length by Layer Report导出方法4.2,方法14.2,方法2B站关注“硬小二”浏览更多演示视频...

无监督对比学习(CL)最新必读经典论文整理分享

对比自监督学习技术是一种很有前途的方法&#xff0c;它通过学习对使两种事物相似或不同的东西进行编码来构建表示。Contrastive learning有很多文章介绍&#xff0c;区别于生成式的自监督方法&#xff0c;如AutoEncoder通过重建输入信号获取中间表示&#xff0c;Contrastive M…...

最长回文子串【Java实现】

题目描述 现有一个字符串s&#xff0c;求s的最长回文子串的长度 输入描述 一个字符串s&#xff0c;仅由小写字母组成&#xff0c;长度不超过100 输出描述 输出一个整数&#xff0c;表示最长回文子串的长度 样例 输入 lozjujzve输出 // 最长公共子串为zjujz&#xff0c;长度为…...

LeetCode 438. Find All Anagrams in a String

LeetCode 438. Find All Anagrams in a String 题目描述 Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

python打卡第47天

昨天代码中注意力热图的部分顺移至今天 知识点回顾&#xff1a; 热力图 作业&#xff1a;对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图&#xff0c;展示模…...