木棍【dfs搜索优化】

木棒

题目描述

在这里插入图片描述

输入样例:

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例:

6
5

【思路】

优化
在这里插入图片描述

在这里插入图片描述

【AC代码】

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 70;int w[N], sum, length, n;
bool st[N];bool dfs(int u, int cur, int start) {	//当前拼接木棒个数,当前木棒长度 ,从第几个已有木棒进行枚举搜索 if(u * length == sum)	return true;// 如果当前木棒的数量 * 长度 = sum,则找到了答案,直接返回 trueif(cur == length) return dfs(u + 1, 0, 0);// 如果当前木棒的长度等于了 length,则新开一根木棒// 否则枚举从 start 开始枚举将哪根木棍拼到当前木棒中for(int i = start; i < n; i ++) {//若已经搜索过 if(st[i] || cur + w[i] > length)	continue;//若没有搜索过st[i] = true;// 继续搜索当前木棒的下一根木棍拼哪根if(dfs(u, cur + w[i], i + 1))	return true;//恢复现场st[i] = false;// 执行到这 dfs(u, s + w[i], i + 1) 为 false: 说明当前木棍搜索失败了//继续进行剪枝优化//如果第一根或者最后一根搜索失败,那么一定失败if(cur == 0 || cur + w[i] == length)	return false;int j = i;
// 		如果当前木棍没有搜到方案,则跳过所有长度相等的木棍while(j < n && w[j] == w[i])	j ++;i = j - 1; }	//若是上边没有匹配成功,则返回失败return false;
}int main() {while(cin >> n, n) {memset(st, 0, sizeof st);sum = 0, length = 1; // 每根木棒的长度从 1 开始枚举,从小到大枚举,题目要求分组最多,那么第一个满足条件的就是答案for(int i = 0; i < n; i ++) {cin >> w[i];sum += w[i];}//从大到小枚举,减少搜索分支 sort(w, w + n, greater<int>());while(true) {// 循环一定会退出,最坏情况下所有木棍拼一根木棒if(sum % length == 0 && dfs(0, 0, 0)) {cout << length << endl;break;}length++;// 当前 length 无法得到答案,则长度 + 1}}return 0;
} 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/298179.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言中的结构体:高级特性与扩展应用

前言 结构体在C语言中的应用不仅限于基本的定义和使用&#xff0c;还包含一些高级特性和扩展应用&#xff0c;这些特性和应用使得结构体在编程中发挥着更加重要的作用。 一、位字段&#xff08;Bit-fields&#xff09; 在结构体中&#xff0c;我们可以使用位字段来定义成员…

CMOS传输门与三态输出门电路

传输门&#xff08;TG&#xff09;的应用比较广泛&#xff0c;在数字电路和模拟电路中均有作用。 在数电中&#xff1a;作为基本单元电路构成各种逻辑电路&#xff1b;在模电中&#xff1a;可在取样-保持电路、斩波电路、数模转换器中传输模拟信号&#xff0c;所以又叫模拟开关…

AssetBundle在移动设备上丢失

1&#xff09;AssetBundle在移动设备上丢失 2&#xff09;Unity云渲染插件RenderStreaming&#xff0c;如何实现多用户分别有独立的操作 3&#xff09;如何在圆柱体类型的地图中编程玩家的输入 4&#xff09;Mixamo动画的根运动问题 这是第380篇UWA技术知识分享的推送&#xff…

【保姆级讲解如何安装与配置Node.js】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

Java中的网络编程(一)

一、网络编程概述 什么是计算机网络把不同区域的计算机&#xff08;广义&#xff09;通过通信设备和线路连接&#xff0c;可以实现数据的传输和共享的系统。实现不同计算机之间的练习&#xff0c;必须有介质连接。网络编程是干什么的聊天-->聊天软件 QQjava语言是支持网络间…

汽车EDI:如何与奔驰建立EDI连接?

梅赛德斯-奔驰是世界闻名的豪华汽车品牌&#xff0c;无论是技术实力还是历史底蕴都在全球汽车主机厂中居于领先位置。奔驰拥有多种车型&#xff0c;多元化的产品布局不仅满足了不同用户画像的需求&#xff0c;也对其供应链体系有着极大的考验。 本文将为大家介绍梅赛德斯-奔驰乘…

MySQL故障排查与生产环境优化

目录 引言 一、故障排查 1.1 故障一 1.2 故障二 1.3 故障三 1.4 故障四 1.5 故障五 1.6 故障六 1.7 故障七 1.8 故障八 1.9 故障九 1.10 故障十 1.11 故障十一 二、 生产环境优化 2.1 硬件优化 2.2 查询优化 总结 引言 MySQL是目前企业最常见的数据库之一&…

【Redis】Redis群集的三种模式(主从、哨兵、群集)

redis群集有三种模式&#xff0c;分别是主从同步/复制、哨兵模式、Cluster&#xff0c;下面会讲解一下三种模式的工作方式&#xff0c;以及如何搭建cluster群集 ●主从复制&#xff1a;主从复制是高可用Redis的基础&#xff0c;哨兵和集群都是在主从复制基础上实现高可用的。主…

MySQL、Oracle查看字节和字符长度个数的函数

目录 0. 总结1. MySQL1.1. 造数据1.2. 查看字符/字节个数 2. Oracle2.1. 造数据2.2. 查看字符/字节个数 0. 总结 databasecharbyteMySQLchar_length()length()Oraclelength()lengthB() 1. MySQL 1.1. 造数据 sql drop table if exists demo; create table demo (id …

软件架构复用

1.软件架构复用的定义及分类 软件产品线是指一组软件密集型系统&#xff0c;它们共享一个公共的、可管理的特性集&#xff0c;满足某个特定市场或任务的具体需要&#xff0c;是以规定的方式用公共的核心资产集成开发出来的。即围绕核心资产库进行管理、复用、集成新的系统。核心…

【Spring】SpringBoot整合MybatisPlus的基本应用

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 一、MybatisPlus简介 先来看一下官方的简介吧。 MyBatis-Plus &#xff08;简称 MP&#xff09;是一个 MyBatis的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为 简化开发、提高效率而生。Myb…

【快速解决】python缺少了PyQt5模块的QtMultimedia子模块

目录 问题描述 问题原因 解决方法 成功示范 问题描述 Traceback (most recent call last): File "d:\桌面\python项目\DesktopWords-master\main.py", line 4, in <module> from PyQt5.QtMultimedia import QMediaPlayer, QMediaContent ModuleNotFoundEr…

OpenCV入门例程:裁剪图片、模糊检测、黑屏检测

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 本例程运行环境为CentOS7&…

深入浅出 -- 系统架构之分布式常见理论概念

随着计算机科学和互联网的发展&#xff0c;分布式场景变得越来越常见&#xff0c;能否处理好分布式场景下的问题&#xff0c;成为衡量一个工程师是否合格的标准。本文我们介绍下分布式系统相关的理论知识&#xff0c;这些理论是我们理解和处理分布式问题的基础。 CAP理论 CAP…

NoSQL之 Redis配置

目录 关系数据库与非关系型数据库 关系型数据库&#xff1a; ●非关系型数据库 关系型数据库和非关系型数据库区别&#xff1a; &#xff08;1&#xff09;数据存储方式不同 &#xff08;2&#xff09;扩展方式不同 对事务性的支持不同 非关系型数据库产生背景 Redis简介…

智能停车场物联网远程监控解决方案

智能停车场物联网远程监控解决方案 智能停车场物联网远程监控解决方案是一种集成了现代物联网技术、大数据分析以及云计算等先进技术手段&#xff0c;对停车场进行全面智能化管理的综合系统。它通过实时感知、精准采集和高效传输各类停车数据&#xff0c;实现对停车场运营状态…

YOLOv3

YOLOv3 论文简介论文内容1. 采用darknet53FPN结构2. 边框预测保持与YOLOv2保持一致3. 沿用YOLOv2 kmeans生成先验anchors4.类别预测改为多分类格式 论文简介 论文&#xff1a;《YOLOv3: An Incremental Improvement》 作者&#xff1a;Joseph Redmon, Ali Farhadi 论文下载地址…

Flume进阶学习!

本文图片来自于8.flume实时监控文件hdfs sink使用演示_哔哩哔哩_bilibili Apache Flume 的启动过程及其配置文件和脚本 在官网下载的Flume的压缩包中&#xff0c;.lib文件有大量的jar包&#xff0c;按道理说只有.lib文件就可以运行Flume程序了。只不过需要java -jar命令还要加…

Vue使用高德地图(快速上手)

1.在高德平台注册账号 2.我的 > 管理管理中添加Key 3.安装依赖 npm i amap/amap-jsapi-loader --save 或 yarn add amap/amap-jsapi-loader --save 4.导入 AMapLoade import AMapLoader from amap/amap-jsapi-loader; 5.直接上代码&#xff0c;做好了注释&#xff08;初…

基于单片机的有害气体检查系统设计

**单片机设计介绍&#xff0c;基于单片机的有害气体检查系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的有害气体检查系统设计旨在实现对环境中各种有害气体的实时监测与报警&#xff0c;保障人员健康和环境…