[蒟蒻Xx_queue学DP] 前置知识:状压DP入门详解 适合新手 来自蒟蒻的状压DP详细总结
转载请注明出处及网页源代码
耗费两节晚自习加一节课填掉了这个坑,感谢观看!制作实属不易,还请多多支持!
看过的小伙伴推荐一下呗!(凑齐5个赞继续更新)
-1.前言
这几天学习了一下状压DP(毕竟CSP初赛就是状压挂掉了),现在也是时候总结一下学习成果,庆祝自己大概学会了状压DP?(雾;
0.概述
这次蒟蒻Xx_queue要和大家一起来学习DP中的很重要的一类:状压DP(状态压缩动态规划);
状压DP，是用二进制来描述状态的一种DP,适用于数据范围比较小的情形,状压DP就是状压+DP;
举个例子:关灯问题:
题目:
现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯是否开，都不管。
现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。
先不管题目说的啥,我们就只考虑怎么状压,也就是怎么用二进制来表示状态:
假设n=5,第1,4,5盏灯亮,第2,3盏灯灭,我们就可以考虑利用一个二进制串:11001来表示这个状态:
| 灯 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|
| 状态 | 1 | 1 | 0 | 0 | 1 |
(0表示灭,1表示亮)
是不是很清晰?
所以这个二进制串:11001
就可以表示这5盏灯目前的状态;(题目后面会讲到)
1.位运算(建议初学者认真研究,这是基础)
相信考过CSP的大家都会
几种位运算的方法如下所示(制表不易):
| 名称 | 符号 | 运算法则 | 举例 |
|---|---|---|---|
| 按位与 | a & b | 相同为1,不同为0 | 00101&11100=00100 |
| 按位或 | a | b | 有1为1,无1为0 | 00101|11100=11101 |
| 按位异或 | a ^ b | 相同为0,不同为1 | 00101^11100=11001 |
| 按位取反 | ~a | 是1为0,是0为1 | ~00101=11010 |
| 左移 | a << b | 把对应的二进制数左移b位 | 00101<<2=0010100 |
| 右移 | a >> b | 把对应的二进制数右移b位 | 00101>>1=0010 |
大概就这样吧……(或者你可以百度百科一下)
2.常用的计算方法:(建议认真食用,灵活运用)
状压DP要求掌握一定的二进制计算方法,所以大家一定要运用熟练(主要还是要多做题)
建议一边看一边手玩一下,举几个例子更便于理解
重点:用二进制表示的集合的基本运算(有待补充)
| 运算 | 计算方法 |
|---|---|
| 集合相交 | x=a&b |
| 集合相并 | x=a|b |
| 枚举子集 | for(int x=sta;x;x=((x-1)&sta)) |
其他运算
可以看看这个图片(来自网络):
也可以看看这些密密麻麻的文字(我是真不想看)(来自网络):
取出x的第i位:\(y=(x>>(i-1))\&1\);
将x第i位取反:$x $ ^ $ = 1<<(i-1)$;
将x第i位变为1:\(x|= 1<<(i-1)\);
将x第i位变为0:\(x\&= ~(1<<(i-1))\);
将x最靠右的1变成0:\(x= x\&(x-1)\);
取出x最靠右的1:\(y=x\&(-x)\);(lowbit函数)
把最靠右的0变成1:\(x|=x+1\)
判断是否有两个连续的1:\(if(x\&(x<<1))\) \(cout<<“YES”;\)
判断是否有