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

acwing算法提高之搜索--剪枝

目录

  • 1 介绍
  • 2 训练

1 介绍

本专题用来记录使用dfs剪枝技巧求解的题目。

剪枝有以下思路:

  1. 优化搜索顺序。
  2. 可行性剪枝。
  3. 最优性剪枝。
  4. 唯一性剪枝,也叫去除冗余。
  5. 记忆化搜索,也叫dp。

2 训练

题目1:165小猫爬山

C++代码如下,

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int N = 20;
int n, m;
vector<int> a;
vector<vector<int>> group;
int res = 20;bool check(int x, int j) {int s = 0;for (auto v : group[j]) s += v;return s + x <= m;
}void dfs(int i, int groupsize) {if (groupsize >= res) {//最优性剪枝return;}if (i == n) {res = groupsize;}int x = a[i];//将x放入哪个组for (int j = 0; j < groupsize; ++j) {//将x放入第j组if (check(x, j)) { //可行性剪枝group[j].emplace_back(x);dfs(i + 1, groupsize);group[j].pop_back();}}//新开一个组group[groupsize].emplace_back(x);dfs(i + 1, groupsize + 1);group[groupsize].pop_back();return;
}int main() {cin >> n >> m;a.resize(n + 1);for (int i = 0; i < n; ++i) cin >> a[i];group.resize(n + 1);sort(a.begin(), a.end());reverse(a.begin(), a.end()); //从大到小枚举,优化搜索顺序//放置原则dfs(0, 0);cout << res << endl;return 0;
}

题目2

相关文章:

acwing算法提高之搜索--剪枝

目录 1 介绍2 训练 1 介绍 本专题用来记录使用dfs剪枝技巧求解的题目。 剪枝有以下思路&#xff1a; 优化搜索顺序。可行性剪枝。最优性剪枝。唯一性剪枝&#xff0c;也叫去除冗余。记忆化搜索&#xff0c;也叫dp。 2 训练 题目1&#xff1a;165小猫爬山 C代码如下&#…...

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:Web)上篇

提供具有网页显示能力的Web组件&#xff0c;ohos.web.webview提供web控制能力。 说明&#xff1a; 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。示例效果请以真机运行为准&#xff0c;当前IDE预览器不支持。 需要权…...

TPU浅谈

前言 大家好&#xff0c;我是jiantaoyab&#xff0c;上篇文章讲了FPGA和ASIC&#xff0c;讲解了 FPGA 如何实现通过“软件”来控制“硬件”&#xff0c;以及我们可以进一步把 FPGA 设计出来的电路变成一块 ASIC 芯片。今天我们来看看TPU。大家可以点击这篇文章TPU深入了解TPU。…...

华为OD机试 - 求字符串中所有整数的最小和(Java JS Python C C++)

题目描述 输入字符串s,输出s中包含所有整数的最小和。 说明: 字符串s,只包含 a-z A-Z 合法的整数包括 1)正整数:一个或者多个0-9组成,如 0 2 3 002 102 2)负整数:负号 – 开头,数字部分由一个或者多个0-9组成,如 -0 -012 -23 -00023 输入描述 包含数字的字符…...

goland设置保存文件时不将4个空格转为TAB

goland设置保存文件时不将4个空格转为TAB 版本&#xff1a;GoLand 2022.3 设置路径&#xff1a; Settings -> Editor -> Code Style -> Go -> Run gofmt图示&#xff1a;...

基于Linux内核的socket编程(TCP)的C语言示例

原文地址&#xff1a;https://www.geeksforgeeks.org/socket-programming-cc/ 服务端&#xff1a; #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/socket.h> #include <unistd.h>#…...

【WEEK3】 【DAY4】JSON交互处理第三部分【中文版】

2024.3.14 Thursday 接上文【WEEK3】 【DAY3】JSON交互处理第二部分【中文版】 目录 6.7.编写抽象类6.7.1.原因6.7.2.新建JsonUtils.java6.7.3.在UserController添加一个方法json6验证抽象类可调用6.7.4.在UserController添加一个方法json7验证该抽象类可复用6.7.5.运行 6.8.…...

下载chromedrive,使用自动化

1、先看一下自己浏览器的版本 2、访问 https://googlechromelabs.github.io/chrome-for-testing/...

D-Star 寻路算法

D-Star 寻路算法 下面简写 D-Star 为 D* D算法&#xff1a;D 算法”的名称源自 Dynamic A Star,最初由Anthony Stentz于“Optimal and Efficient Path Planning for Partially-Known Environments”中介绍。它是一种启发式的路径搜索算法&#xff0c; 适合面对周围环境未知或者…...

mysql5.7编译安装

MySQL 5.7在不同操作系统上的编译安装过程略有不同,以下是在Linux系统上编译安装MySQL 5.7的一般步骤: 1. 安装编译所需的依赖包 sudo yum install gcc-c cmake ncurses-devel bison openssl-devel 2. 下载MySQL源码包和Boost库并解压 wget https://dev.mysql.com/get/Dow…...

Java项目实战记录:雷达数据渲染

目录 Java项目实战记录&#xff1a;雷达数据渲染业务背景代码逻辑数据结构颜色渲染MapContent加载数据并输出截图 完整代码GenerateMapImage地图渲染工具测试代码 渲染效果 Java项目实战记录&#xff1a;雷达数据渲染 业务背景 我之前已经成功使用Java语言解析了C处理的雷达数…...

进程的概念 | PCB | Linux下的task_struct | 父子进程和子进程

在讲进程之前首先就是需要去回顾一下我们之前学的操作系统是干嘛的&#xff0c;首先操作系统是一个软件&#xff0c;它是对上提供一个良好高效&#xff0c;稳定的环境的&#xff0c;这是相对于用户来说的&#xff0c;对下是为了进行更好的软硬件管理的&#xff0c;所以操作系统…...

【GPT-SOVITS-03】SOVITS 模块-生成模型解析

说明&#xff1a;该系列文章从本人知乎账号迁入&#xff0c;主要原因是知乎图片附件过于模糊。 知乎专栏地址&#xff1a; 语音生成专栏 系列文章地址&#xff1a; 【GPT-SOVITS-01】源码梳理 【GPT-SOVITS-02】GPT模块解析 【GPT-SOVITS-03】SOVITS 模块-生成模型解析 【G…...

2024HVV行动-进军蓝中研判(log4j2、fastjson、Struts2、Shiro)

1、log4j2 特征&#xff1a; 恶意请求中包含 JNDI 协议地址&#xff0c;如"ldap://"、"rmi://"等&#xff0c;被 log4j2 解析为 JNDI 查找。 原理&#xff1a; 在日志输出中&#xff0c;未对字符进行严格的过滤&#xff0c;执行了 JNDI 协议加载的远程恶…...

亮点抢先看!4月16-17日,百度Create大会开设“AI公开课”,大咖带你打造赚钱工具

3月16日&#xff0c;2024百度Create AI开发者大会正式开放售票&#xff0c;嘉宾套票定价399元。据悉&#xff0c;本次大会以“创造未来&#xff08;Create the Future&#xff09;”为主题&#xff0c;设有20深度论坛、超30节AI公开课、3000平AI互动体验区和AI音乐节等精彩环节…...

【笔记本清灰/实用经验】荣耀Magicbook14-2020款-R5-4500U-清灰实战

清灰有风险&#xff0c;动手需谨慎&#xff0c;本文只分享本人的清灰过程&#xff0c;对使用它所产生的任何后果不任何负责任 文章目录 背景信息准备阶段工具准备信息收集 正式清灰初始化清灰流程放掉身体的静电&#xff08;重要&#xff09;拆笔记本后盖断开电源&#xff08;重…...

如何写好Stable Diffusion的prompt

Stable Diffusion是一种强大的文本到图像生成模型&#xff0c;其效果在很大程度上取决于输入的提示词&#xff08;Prompt&#xff09;。以下是一些关于如何编写有效的Stable Diffusion Prompt的秘诀&#xff1a; 明确描述&#xff1a;尽量清晰地描述你想要的图像内容。使用具体…...

计算机毕业设计 | SpringBoot+vue 移动端社区物业管理系统(附源码+论文)

1&#xff0c; 概述 课题背景 近几年来&#xff0c;随着物业相关的各种信息越来越多&#xff0c;比如报修维修、缴费、车位、访客等信息&#xff0c;对物业管理方面的需求越来越高&#xff0c;我们在工作中越来越多方面需要利用网页端管理系统来进行管理&#xff0c;我们所需…...

玩转C语言——数组初探

一、前言 通过前面的学习&#xff0c;我们已了解C语言的结构变量、分支结构和循环结构。今天&#xff0c;我们一起来认识C语言的另一知识点——数组。先赞后看&#xff0c;养成习惯。 二、数组概念 学习数组&#xff0c;我们要明白数组是什么。在我看来&#xff1a;数组是⼀组…...

Nginx指令配置大全

基本命令 nginx -t 检查配置文件是否有语法错误 nginx -s reload 热加载&#xff0c;重新加载配置文件 nginx -s stop 快速关闭 nginx -s quit 等待工作进程处理完成后关闭配置块介绍 全局块 全局块是默认配置文件从开始到events块之间的…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...