关键词：
2018过农历新年这几天，学了一下状态压缩动态规划，现在先总结一下。
状态压缩其实是一种并没有改变dp本质的优化方法，阶段还是要照分，状态还是老样子，决策依旧要做，转移方程还是得列，最优还是最优，无后还是无后，所以它比较好理解。
状压，顾名思义就是要将一些状压想办法压缩起来（可以压，也可以删）。其中这些状态都满足相似性和数量很多。这样才好压而且压得有意义。常见于一般的方格题，网络题等等。
所以一般基础的状压就是将一行的状态压成一个数，这个数的二进制形式反映了这一行的情况。所以位运算可以帮助我们解决很多问题。我看了一篇讲义，感觉挺好的，就直接拿来用了，这里会介绍二进制的基本操作和一些常见用法。
这些操作都是在一个数转成二进制的情况下做的，包括按位与&、或|、取反~（注意负数补码的符号）、异或^（不同则真）、左移<<、右移>>。
下面是由江苏省淮阴中学薛志坚整理的一些常见操作：
接下来就是进行普通dp的操作。
不过这里要注意几点
初试化状态的时候要看清条件，什么要，什么不要。
一般情况下要预处理前k行（k由题目定）。
Dp时题目给的条件和fit函数、state数组都要检查。
最最重要的一点：位反（~ ) > 算术 > 位左移、位右移 > 关系运算
> 位与 > 位或 > 位异或 > 逻辑运算
所以一般位运算最好打括号。
讲讲不常规的状压dp。
我们要找一个方法将多余的状态给砍掉或者缩成一段。
上例题：
1、Corn Fields
最基础的状压dp，很多时候可以用来作为模板借鉴着做其他题目。
详情请看：http://www.cnblogs.com/Ronald-MOK1426/p/8451875.html
2、互不侵犯King
好像是优化搜索，其实还是dp，不过这里比t1的条件多了、难了，也比t1多限定了一个国王数量，所以要多存一个国王数量的状态，但是其实还是很基础。
详情请看：http://www.cnblogs.com/Ronald-MOK1426/p/8456798.html
3、炮兵阵地
这里从一个单行状态变成了双行状态，其他都很模板。
详情请看：http://www.cnblogs.com/Ronald-MOK1426/p/8456834.html
4、过河
这是第一道升级的状压，它终于不是普通01串的状态，而是将没用的状态给直接砍掉，再进行dp
详情请看：http://www.cnblogs.com/Ronald-MOK1426/p/8456860.html
5、强迫症的炸山
这是我同学（一位大佬）lxy出的题，这道看似很简短、很简单的题，做起来却不是那么容易。我甚至还没找到怎么正确地压缩状态。至今未果，以后会慢慢补充。毕竟现在打暴力得了tle，打正解（手动划去）得了re，我也很无奈。
状压dp其实不止这么简单，我这次学了只是皮毛中的皮毛，状压要捉住怎么压缩状态，加快程序运行，别的就和普通dp一样了。
请各位大佬指出错误或补充，谢谢。
嗯，就这样了。
状压dp基础总结(代码片段)
这篇博客是参照另一篇博客写的:这是另一个博客的地址:https://www.cnblogs.com/Ronald-MOK1426/p/8456945.html首先我做过的几道题目:poj1185炮兵阵地:1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm> 查看详情
状压dp(代码片段)
这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09 00001001&5 000001011 &nb 查看详情
动态规划---状压dp2(代码片段)
今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情
状压dp总结(代码片段)
...第三四个没被占用，第五六七个被占用我们知道位运算和状压DP一样，也是在二进制下进行的，所以位运算往往可以解决很多问题我们来看看状压DP（位运算）的常用操作：有了这些位运算的帮助，我们便可以更加容易的对每一... 查看详情
动规大总结(代码片段)
...总结得非常好： 自为风月马前卒大佬，FlashHu大佬。状压DP状压DP主要适用于数据范围很小以至于可以直接把当前状态作为下标的题目。“数组的定义及状态之间的转移方程”是答题的关键，另外根据题目的特殊条件做... 查看详情
莫队算法·初探总结(代码片段)
莫队算法分那么几类：普通序列带修改树上回滚支持在线其实上述的类型还可以组合起来（非常的毒瘤）。个人理解莫队算法的精髓在于如何利用暴力将答案再合理的时间和空间内跑出来。说白了：[莫队算法=一种很牛逼的自定... 查看详情
[dp总结]状压dp(代码片段)
顾名思义，是用将状态进行二进制压缩成集合的形式来方便DP转移的方法。一些常用的代码表示如下i&j//取状态i,j重合部分i^j//取状态i,j不同部分i|j//合并状态i,j(1<<N)-1//表示111…1(N个1)1<<i-1//表示00100…0(1后面有i-1个0，... 查看详情
状压dp小结
1.要状压的那一维，所有有关的下标要从0开始，而不是从1开始2.预处理很重要，可以说基本所有的状压dp都要有预处理这玩意 查看详情
hoj2662经典状压dp//myfirst状压dp
题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言：用dp解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。但是有这样的一类题目，它们具有dp问题的特性，但状态中所包含的信息过多，... 查看详情
强连通分量算法·$tarjan$初探(代码片段)
嗯，今天好不容易把鸽了好久的缩点给弄完了……感觉好像……很简单？算法的目的，其实就是在有向图上，把一个强连通分量缩成一个点……然后我们再对此搞搞事情，(over)哦对，时间复杂度很显然是(Theta(n))的，懒得(Proof)了... 查看详情
foreignnumber[状压dp]
...leInput 123455SampleOutput 24HINT Solution 我们运用状压DP，令f[j][opt]表示当前余数为j，状态为opt的方案。 状态记录的是：各个数字被用了几次。 那么我们就可以状压了。先 查看详情
第一次接触状压dp(代码片段)
状压DP入门及理解*（另类的暴力）* 一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。 状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。 &... 查看详情
算法复习——状压dp
状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····... 查看详情
fzu2188状压dp
G-SimpleStringProblemTimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示： 转移方程：i是当前节点，j是下一步要走的节点 子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情
d.romanandnumbers(状压dp)(代码片段)
D.RomanandNumbers(状压dp)把nnn的每一位状压，问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情
poj2411mondriaan'sdream（状压dp）
【POJ2411】Mondriaan‘sDream（状压dp）TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情
simplestringproblem（状压dp）(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情