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

xmuoj [蒙德里安的梦想] 状压dp个人笔记

本题是状压dp经典题目,很多人都是通过这一题开始对状压dp有所了解。

在进行讲解之前,我们先通过几个问答大致了解状压dp。

一、问答

1.  问题:什么是状压dp?

     回答:状压dp即为状态压缩动态规划,何为状态压缩?怎么进行状态压缩?是个问题。

这个问题涉及到了状压dp的核心思想——把问题的状态压缩成整数,因为整数便于存储和进行状态转移。

2.  问题:状压dp状态的存储形式是?

     回答:前面已经说了,问题的状态应该压缩成整数,但是单纯的10进制整数显然无法满足最小子问题的状态存储,或者说,浪费了很多存储空间。对于最小子问题,一般情况下,只有 1 和 0 两种状态,那么,我们用二进制存储显然更优。

3.  问题:用二进制存储状态只是存储上更优吗?

     回答:不然,二进制天然的位运算可以大大加速状态转移。这也是状压dp不会超时的重要原因。

哈哈,关键词get到了吗?二进制、位运算 ✿✿ヽ(°▽°)ノ✿

二、下面进行例题讲解

        错误思路我就不讲了,因为错误思路千奇百怪,我也是开始就想偏了(我上来就是dp[n][m]一顿转移)。

        首先,我们应该明白的是,我们只能放横着放或者竖着放长方形,一旦横着放的确定了(横着的放法要在合理情况下,总不能让竖的放不了吧O(∩_∩)O ),那么竖着的一定就只有一种可能了,所以,我们只需考虑横着放有多少种合理的放法即可。

下面该怎么做呢?已经焦头烂额了,开始吟唱

对于第 i 列,我们假设 0~ i -1 列的横着放的长方形已经全部放好了,我们都知道,横着放的一定有突出的部分。

就比如说,对于这张图,第 i 列突出的部分是 0、1、3这三个位置,用二进制表示即为101100,对应十进制的44,所以,这个状态就是 f [ i ][ 44 ]

不难发现,第 i 列状态是由第 i-1 列的状态转移过来的

具体来说,f [ i ][ j ] +=所有满足条件的 f[ i-1][ k ] 

要满足什么条件呢?

1. j 和 k不能重叠(显然长方形不能重叠放置,可以重叠的话放法就无穷尽了)

对于这个条件,保证 j&k==0 即可

2. j和k放完之后,第i-1列不能有连续奇数个0(因为这样就放不了竖着的了)

定义isok[ i ]表示 i 的二进制表示是否满足上述条件,isok[ i ] = true表示满足条件,

保证 isok[ j | k ]为 true 即可

三、C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
bool isok[M];
long long f[N][M];
int main() {while (cin >> n >> m, n || m) {for (int i = 0;i < 1<<n;i++) {//计算isok[i]isok[i] = true;int cnt = 0;for (int j = 0;j < n;j++) {if (i >> j & 1) {if (cnt % 2)isok[i] = false;cnt = 0;}else cnt++;}if (cnt % 2)isok[i] = false;}memset(f, 0, sizeof f);f[0][0] = 1;for (int i = 1;i <=m;i++) {for (int j = 0;j < 1<<n;j++) {for (int k = 0;k < 1<<n;k++) {if (isok[j | k] && !(j & k)) {//满足两个条件才能转移f[i][j] += f[i - 1][k];}}}}cout << f[m][0] << endl;//代表到 m列且没有突出的情况(列数为0~m-1,m列表示遍历完成了)}return 0;
}

四、结尾

写完再回首,不禁又感叹状压dp的巧妙,如此优雅,妙哉妙哉。

这就是今天要分享的内容,感谢观看!

相关文章:

xmuoj [蒙德里安的梦想] 状压dp个人笔记

本题是状压dp经典题目&#xff0c;很多人都是通过这一题开始对状压dp有所了解。 在进行讲解之前&#xff0c;我们先通过几个问答大致了解状压dp。 一、问答 1. 问题&#xff1a;什么是状压dp? 回答&#xff1a;状压dp即为状态压缩动态规划&#xff0c;何为状态压缩&#x…...

ubuntu22安装搜狗输入法不能输入中文

关闭Wayland 在/etc/gdm3/custom.conf文件内&#xff0c;取消注释WaylandEnable cat /etc/gdm3/custom.conf | grep WaylandEnable WaylandEnablefalse 其它步骤参考搜狗官方教程 https://pinyin.sogou.com/linux/help.php...

HtmlAgilityPack 操作详解

目录 1.安装 HtmlAgilityPack 2. 示例 HTML 3. 使用 HtmlAgilityPack 进行 HTML 解析与操作 4. 代码详解 1.加载html文档 2.选择元素 3. 提取属性 4.修改属性 5.常用的几种获取元素的 XPath 写法 HtmlAgilityPack&#xff1a; 轻量且高效&#xff0c;适合进行常规的 H…...

基于SSM医院门诊互联电子病历管理系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;医生管理&#xff0c;项目分类管理&#xff0c;项目信息管理&#xff0c;预约信息管理&#xff0c;检查信息管理&#xff0c;系统管理 用户账号功能包括&#xff1a;系统首页&…...

【读书笔记/深入理解K8S】集群网络

前言 上一章讲了集群控制器的一个大概的原理&#xff0c;这一章讲一下集群网络。网络是集群通信的载体&#xff0c;因为该书是阿里云团队出品的&#xff0c;所以也以阿里云的集群网络方案为例&#xff0c;其他云厂商的网络集群方案一般来说也大同小异。所以通过本章的学习&…...

【专有网络VPC】连接公网

通过ECS实例固定公网IP、弹性公网IP、NAT网关、负载均衡使专有网络中的云资源可以访问公网&#xff08;Internet&#xff09;或被公网访问。 概述 专有网络是您自定义的云上私有网络。专有网络中的云资源默认无法访问公网&#xff0c;也无法被公网访问。您可以通过配置ECS实例…...

论文 | Legal Prompt Engineering for Multilingual Legal Judgement Prediction

这篇文章探讨了如何利用“法律提示工程”&#xff08;LPE&#xff09;来指导大型语言模型&#xff08;LLM&#xff09;进行多语言法律判决预测&#xff08;LJP&#xff09;。主要内容&#xff1a; LPE 的概念&#xff1a; LPE 是指通过设计特定的提示&#xff08;promp…...

国科安芯抗辐照MCU和CANFD芯片发布

国科安芯科技有限公司近期发布了两款重要的芯片产品&#xff1a;抗辐照MCU芯片和抗辐照CANFD芯片。这两款芯片的发布标志着国科安芯在高性能、高安全性芯片产品研制方面取得了显著进展&#xff0c;特别是在抗辐照技术领域。 1. 抗辐照MCU芯片&#xff1a;国科安芯研发的AS32A4…...

C++ 并发专题 - 无锁数据结构(概述)

一&#xff1a;概述&#xff1a; 无锁数据结构是一种在多线程环境中实现线程安全的结构&#xff0c;它允许多个线程在没有传统锁机制的情况下并发访问和修改数据。这种设计的目标是提高程序的性能和响应性&#xff0c;避免锁竞争和上下文切换的开销。 二&#xff1a;原理&…...

NLP领域的经典算法和模型

在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;经典算法和模型众多&#xff0c;它们在不同任务中发挥着重要作用。以下是一些NLP领域的经典算法和模型的详细介绍&#xff1a; 一、基础模型 词袋模型&#xff08;Bag of Words&#xff0c;BoW&#xff09; 原理&a…...

提升安全上网体验:Windows 11 启用 DOH(阿里公共DNS)

文章目录 阿里公共 DNS 介绍免费开通云解析 DNS 服务Windows 编辑 DNS 设置配置 IPv4配置 IPv6 路由器配置 DNS 阿里公共 DNS 介绍 https://alidns.com/ 免费开通云解析 DNS 服务 https://dnsnext.console.aliyun.com/pubDNS 开通服务后&#xff0c;获取 DOH 模板&#xff0…...

论文概览 |《Journal of Transport Geography》2024.10 Vol.120

本次给大家整理的是《Journal of Transport Geography》杂志2024年9月第120卷的论文的题目和摘要&#xff0c;一共包括17篇SCI论文&#xff01; 论文1 Modelling scenarios in planning for future employment growth in Stockholm 斯德哥尔摩未来就业增长规划情景建模 【摘要…...

yum不能使用: cannot find a valid baseurl for repo: base/7/x86_64

使用yum命令时报错&#xff1a; 原因&#xff1a; CentOS 已经停止维护的问题。2020 年 12 月 8 号&#xff0c;CentOS 官方宣布了停止维护 CentOS Linux 的计划&#xff0c;并推出了 CentOS Stream 项目&#xff0c;CentOS Linux 8 作为 RHEL 8 的复刻版本&#xff0c;生命周期…...

什么品牌的护眼台灯比较好?五款护眼效果比较明显的护眼台灯

在当今信息爆炸的时代背景下&#xff0c;挑选一款真正符合个人需求的护眼台灯&#xff0c;确实是一项不小的挑战。市场上品牌众多、型号繁杂&#xff0c;功能特点各不相同&#xff0c;价格区间也相当广泛&#xff0c;许多消费者在选购时往往感到迷茫不已。当大家询问“什么品牌…...

HTML 表单设计与验证

创建 HTML 表单的步骤如下&#xff1a; 使用 <form> 标签来创建表单&#xff0c;<form> 标签有一个 action 属性&#xff0c;用于指定表单提交的目标 URL。 在 <form> 标签内部&#xff0c;使用 <input> 标签来创建输入框。<input> 标签有一个 …...

qt QDialog详解

1、概述 QDialog是Qt框架中用于创建对话框的类&#xff0c;它继承自QWidget。QDialog提供了一个模态或非模态的对话框&#xff0c;用于与用户进行交互。模态对话框会阻塞其他窗口的输入&#xff0c;直到用户关闭该对话框&#xff1b;而非模态对话框则允许用户同时与多个窗口进…...

supervisor服务“Exited too quickly“解决方案

【初始问题】supervisor创建一个守护进程&#xff0c;老是提示启动失败 【结论】进程执行后&#xff0c;短时间就断开了 Ⅰ 问题分析 supervisor开启进程守护失败了&#xff0c;查看下进程执行记录&#xff0c;显示这个进程的指令执行报错了 接下来&#xff0c;查看下superv…...

动态规划 —— 路径问题-地下城游戏

1. 地下城游戏 题目链接&#xff1a; 174. 地下城游戏 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/dungeon-game/description/ 2. 算法原理 状态表示&#xff1a;以莫一个位置位置为结尾或者以莫一个位置为起点 dp[i&#xff0c;j]表示&#xff1a…...

沈阳乐晟睿浩科技有限公司抖音小店短视频时代的电商蓝海

在数字化浪潮席卷全球的今天&#xff0c;电子商务以其独特的魅力和无限的潜力&#xff0c;成为了推动经济发展的新引擎。作为这一领域的佼佼者&#xff0c;沈阳乐晟睿浩科技有限公司凭借其深厚的行业积淀与创新精神&#xff0c;正逐步成为众多商家在抖音小店平台上腾飞的强大助…...

ubuntu20.04安装ros与rosdep

目录 前置配置 配置apt清华源 配置ros软件源 添加ros安装源&#xff08;中科大软件源&#xff09; 设置秘钥 更新源 ros安装 安装ros 初始化 rosdep 更新 rosdep 设置环境变量 安装 rosinstall 安装验证 启动海龟仿真器 操控海龟仿真器 rosdep安装更新 安装 使用…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

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

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

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...