yyx的个人主页
yyx的个人主页
返回首页
无标题
发表于
2026-06-08
|
更新于
2026-06-25
|
浏览量:
文章作者:
dream_empty
文章链接:
http://dreamempty.xyz/2026/06/08/birth/
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
yyx的个人主页
！
下一篇
进阶算法2: 状压dp
状压 DP一、原理介绍状态压缩动态规划（状压 DP） 是一种将集合或状态用二进制位进行压缩表示的动态规划方法。它适用于 维度较小（通常 n≤20）但需要记录多个元素“选/不选”或“存在/不存在”等信息的组合优化问题。 通过将每个元素映射到一个二进制位，可以用一个整数表示一个子集或状态，从而在 DP 中进行高效的转移。 常用位运算操作 操作 代码 含义 将第 $i$ 位设为 1 mask | (1 << i) 选中元素 i 将第 $i$ 位设为 0 mask & ~(1 << i) 移除元素 i 检查第 $i$ 位是否为 1 mask & (1 << i) 判断元素 i 是否存在 翻转第 $i$ 位 mask ^ (1 << i) 切换元素 i 的状态 检查是否有连续的 1 mask & (mask >> 1) 若结果为 0 则无相邻的 1（常用于棋盘问题） 去掉最低位的 1 mask & (mask - 1) lowbit 操作，常用于枚举...
dream_empty
记录一下来时路
文章
12
标签
12
分类
0
Follow Me
公告
This is my Blog
最新文章
无标题
2026-06-08
进阶算法2: 状压dp
2026-05-26
进阶算法1: 线段树
2026-05-14
游戏资源1: 残梦孤域
2026-05-04
基础算法7:最小生成树
2026-05-03
