day 33 状态压缩dp
二维状态压缩dp
对于解决哈密顿回路问题的状态压缩dp只能计算固定起点到其他点的总方案数或最小路径等
回路计数
小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼
(即走一条哈密尔顿回路)
可看做:从第一栋开始到 遍历完其他的所有方案数

状态压缩从第0位开始,因此在初始化邻接矩阵时要转换一下
#include <bits/stdc++.h>
using namespace std; long long a[22][22], dp[1 << 22][22], ans;
//dp[i][j]:i种状态,走到教学楼j的方案数 (数组稍微开大一点)
int main()
{for(int i = 1; i <= 21; i++)for(int j = 1; j <= 21; j++)if(__gcd(i, j) == 1) a[i - 1][j - 1] = a[j - 1][i - 1] = 1;//从第0位开始 dp[1][0] = dp[0][1] = 1;//2楼到1楼 // 共2^21-1(即全1)种状态 for(int i = 1; i <= (1 << 21) - 1; i++){//考察状态i for(int j = 0; j < 21; j++){//走到教学楼j if(! (i >> j & 1)) continue; //如果状态i不经过教学楼jfor(int k = 0; k < 21; k++){if((i >> k & 1) || ! a[j][k])continue;//如果状态i已经过k或者楼jk之间无路//从新状态i+1<<k,到楼k的方案数 = i到k + i到j到k dp[i + (1 << k)][k] += dp[i][j]; } }}for(int i = 0; i < 21; i++)ans += dp[(1 << 21) - 1][i];//全1状态,最后一次经过i楼,然后最后回到1楼(因为1与所有数互质所以一定有路) cout << ans << endl; return 0;
}吃奶酪
房间里放着 n块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 (0,0) 点处。
固定起点(0, 0),遍历,最短路径
memset(a, 127, sizeof(a))
https://www.cnblogs.com/ljysy/p/12535388.html
https://blog.51cto.com/u_3044148/4005292
#include <bits/stdc++.h>
using namespace std;double x[20], y[20], dp[20][(1 << 15) + 15];
int n;
double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];memset(dp, 127, sizeof(dp));//设置各状态距离 for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++)//状态:在i点直接到j距离dp[i][j] dp[i][j] = dp[j][i] = dis(i, j); for(int i = 1; i < (1 << n); i++){//遍历所有状态 for(int j = 1; j <= n; j++){ if(! (1 & (i >> (j - 1)))) continue;//不过第j块奶酪 //if(! (i & (1 << (j - 1)))) continue; //相当于上面 for(int k = 1; k <= n; k++){ if(k == j || !(1 & (i >> (k - 1)))) continue;//与j同或该状态不过第k块 dp[j][i] = min(dp[j][i], dp[k][i - (1 << (j - 1))] + dis(j, k));//i-k-j } }} double ans = 1e9;for(int i = 1; i <= n; i++)ans = min(ans, dp[i][(1 << n) - 1] + dis(i, 0));//从(0,0)开始 printf("%.2lf\n", ans);return 0;
}郊区春游
#include <bits/stdc++.h>
using namespace std; int n, m, r, vis[205], dis[205][205], edge[20][20], dp[205][(1 << 15) + 15];
int main()
{memset(dp, 127, sizeof(dp));cin >> n >> m >> r;for(int i = 1; i <= r; i++) cin >> vis[i];for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dis[i][j] = 1e9;//从i到j最短距离初始化(无穷大:ij间没有路) int a, b, c;for(int i = 0; i < m; i++){cin >> a >> b >> c;dis[a][b] = dis[b][a] = c;//有路}//floyd求i到j最短距离for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(dis[i][j] > dis[i][k] + dis[k][j])dis[i][j] = dis[i][k] + dis[k][j];}}} //把点转化为 1 2 3 4 ... r:问题变为从固定点走,经过每个点过一次距离最短多少?for(int i = 1; i <= r; i++)for(int j = 1; j <= r; j++)edge[i][j] = dis[vis[i]][vis[j]];// tsp状态压缩dpfor(int i = 1; i < (1 << r); i++){for(int j = 1; j <= r; j++){//状态为i时走到点j if(!(i & (1 << (j - 1)))) continue;//状态i不过点jif(i == (1 << (j - 1))){ dp[j][i] = dp[i][j] = 0;continue;}//起点 for(int k = 1; k <= r; k++){//不过j,从k到j if(dp[j][i] > dp[k][i - (1 << (j - 1))] + edge[j][k])dp[j][i] = dp[k][i - (1 << (j - 1))] + edge[j][k];}} }int ans = 1e9;for(int i = 1; i <= r; i++)ans = min(ans, dp[i][(1 << r) - 1]);cout << ans << endl; return 0;
}一维状态压缩dp
[蓝桥杯 2019 省 A] 糖果
总共m种糖果,状态有2^m - 1种情况
#include <bits/stdc++.h>
using namespace std; int n, m, k, tt, t, a[105], dp[1 << 20];
int main()
{cin >> n >> m >> k;memset(dp, -1, sizeof(dp)); //买不到全部则输出-1 for(int i = 0; i < n; i++){tt = 0;for(int j = 0; j < k; j++){cin >> t;tt = tt | (1 << (t - 1)); //二进制表示第i包糖果中有哪几种糖果 }a[i] = tt, dp[tt] = 1;//状态tt最少需1包 }for(int i = 0; i < n; i++){for(int j = 0; j < (1 << m); j++){if(dp[j] == -1) continue;//没有该组合(状态)else if(dp[j | a[i]] == -1) dp[j | a[i]] = dp[j] + dp[a[i]];//新状态无记录 else dp[j | a[i]] = min(dp[j | a[i]], dp[j] + dp[a[i]]); //有记录,记录最小的 }}cout << dp[(1 << m) - 1] << endl;//输出买到所有糖果的最少包数 return 0;
}
相关文章:
day 33 状态压缩dp
二维状态压缩dp对于解决哈密顿回路问题的状态压缩dp只能计算固定起点到其他点的总方案数或最小路径等回路计数小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼(即走一条哈密尔顿回路)可看做࿱…...
扬帆优配|超3600股飘绿,人民币贬值近300点!外资净卖近38亿
今天早盘,A股整体震动调整,白马蓝筹股体现较弱,上证50、沪深300指数均跌超1%。 盘面上,国防军工、造纸、数字钱银、IT设备等板块逆势活跃,酿酒、酒店餐饮、钙钛矿电池、有色等板块跌幅居前。两市半日成交4577亿&#x…...
【编程基础之Python】6、Python基础知识
【编程基础之Python】6、Python基础知识Python基础知识Python的基本要素模块语句表达式注释Python的代码格式Python基础知识 Python 是一种高级的、动态的、解释型的编程语言,具有简单易学、开发效率高、可读性强等特点,广泛应用于数据科学、Web 开发、…...
selenium基本操作
爬虫与反爬虫之间的斗争爬虫:对某个网站数据或图片感兴趣,开始抓取网站信息;网站:请求次数频繁,并且访问ip固定,user_agent也是python,开始限制访问;爬虫:通过设置user_a…...
思科设备命令讲解(超基础二)
♥️作者:小刘在C站 ♥️个人主页:小刘主页 ♥️每天分享云计算网络运维课堂笔记,努力不一定有收获,但一定会有收获加油!一起努力,共赴美好人生! ♥️夕阳下,是最美的绽放࿰…...
HTML基础(3)
HTML基础单选框、复选框、下拉框文本框< script >标签属性< script >基本使用单选框、复选框、下拉框 文本框 < script >标签属性 type属性定义script元素包含或src引用的脚本语言。属性值是MIME类型,包括text/javascript,text/ecmascript, appl…...
鸿蒙3.0 APP混合开发闪退问题笔记
APP采用cordova混合开发, 鸿蒙2.0以及安卓操作系统正常使用,但是在鸿蒙3.0中出现APP闪退,对APP进行真机调试发现,鸿蒙3.0系统对crosswork插件存在兼容问题,这些问题会导致APP页面加载失败,进而导致App闪退测…...
批量操作文件功能-课后程序(JAVA基础案例教程-黑马程序员编著-第七章-课后作业)
【实验7-1】 批量操作文件功能 任务介绍 1.任务描述 在日常工作中,经常会遇到批量操作系统文件的事情,通常情况下,只能手动重复的完成批量文件的操作,这样很是费时费力。本案例要求编写一个文件管理器,…...
Hadoop3.3.1完全分布式部署
Hadoop目录Hadoop3.3.1完全分布式部署(一)1、HDFS一、安装1、基础安装1.1、配置JDK-181.2、下载并解压hadoop安装包本地运行模式测试 eg:2、完全分布式运行模式1、概要:2、编写集群分发脚本,把1~4步安装的同步到其他服务器:2.1、创建脚本vim …...
SpringMVC中的注解
SpringMVC中的注解 文章目录SpringMVC中的注解RequestMapping注解RequestMapping中的value属性RequestMapping中的method属性派生类PathVariable注解RequestParam注解RequestMapping注解 RequestMapping中的value属性 RequestMapping:既可以标识在方法上也可以标识…...
python+Vue学生作业系统 django课程在线学习网站系统
系统分为学生,教师,管理员三个角色: 学生功能: 1.学生注册登录系统 2.学生查看个人信息,修改个人信息 3.学生查看主页综合评价,查看今日值班信息 4.学生在线申请请假信息,查看请假的审核结果和请…...
CSS 美化网页元素【快速掌握知识点】
目录 一、为什么使用CSS 二、字体样式 三、文本样式 color属性 四、排版文本段落 五、文本修饰和垂直对齐 1、文本装饰 2、垂直对齐方式 六、文本阴影 七、超链接伪类 1、语法 2、示例 3、访问时,蓝色;访问后,紫色; …...
Tableau连接openGauss实践
目录 一、摘要 二、什么是Tableau? 三、安装Tableau 四、安装ODBC驱动 1、openGauss数据库 2、连接前置条件 3、Tableau连接openGauss方式一 4、Tableau连接openGauss方式二 一、摘要 Tableau可以连接到多种数据库,包括关系型数据库࿰…...
RabbitMQ 实现延迟队列
业务场景:1.生成订单30分钟未支付,则自动取消,我们该怎么实现呢?2.生成订单60秒后,给用户发短信1 安装rabbitMqwindows安装ubuntu中安装2 添加maven依赖<!-- https://mvnrepository.com/artifact/org.springframework.boot/spr…...
Spring Bean 生命周期,好像人的一生
简单说说IoC和Bean IoC,控制反转,想必大家都知道,所谓的控制反转,就是把new对象的权利交给容器,所有的对象都被容器控制,这就叫所谓的控制反转。 控制反转 Bean,也不是什么新鲜玩意儿…...
C++算法基础课 05 —— 数据结构1_单链表/双链表/栈/单调栈/队列/单调队列/KMP
文章目录 1. 单链表(用数组模拟链表)1.1 模板1.1.1 插入操作1.1.2 删除操作1.2 习题1 —— 826.单链表2. 双链表2.1 模板2.1.1 插入操作2.1.2 删除操作2.2 习题1 —— 827.双链表3. 栈(用数组模拟栈)3.1 模板3.2 习题1 —— 828.模拟栈4. 单调栈4.1 模板4.2 习题1 —— 830.单调…...
小型水库大坝安全监测的主要对象
一、监测背景 大坝监测的目的分成两个大的方面,一方面是为了验证设计、指导施工、为科研提供必要的资料;另一方面,也可以说是更重要的方面,就是为了长期监视大坝的安全运行。因此,一个成功的监测设计者不仅要能充分领会…...
常见软件开源(alpha,beta等)版本介绍
一、开发期Alpha:是内部测试版,一般不向外部发布,会有很多Bug.一般只有测试人员使用。Beta:也是测试版,这个阶段的版本会一直加入新的功能。在Alpha版之后推出。-RC(ReleaseCandidate):最终测试版本;可能成为最终产品的…...
凌恩生物资讯|抗性宏基因组又一力作|抗性基因+可移动元件研究新成果!
凌恩生物合作客户:合肥工业大学崔康平老师团队利用凌恩生物宏基因组抗性基因研究解决方案,对污水处理厂活性污泥中的钆(Gd(III))和抗生素磺胺甲噁唑(SMX)的联合污染情况进行了调查&a…...
常见前端基础面试题(HTML,CSS,JS)(二)
ES6 新增哪些东西 箭头函数字符串模板支持模块化(import、export)类(class、constructor、extends)let、const 关键字新增一些数组、字符串等内置构造函数方法,例如 Array.from、Array.of 、Math.sign、Math.trunc 等…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
