状压dp

应用背景以集合为状态，集合一般可以用二进制表示，用二进制的位运算处理
集合问题一般是指数复杂度的，例如：1.子集问题，设n个元素没有先后关系，那么一共有 \(2^n\) 个子集；2.排列问题，对所有n个元素进行全排列，共有 \(n!\) 个排列
状态压缩：主要就是dp的一种状态，与dp转移关系不大
位运算：\(a\&(a-1)\) 把a的最后一个1去掉

P10447 最短 Hamilton 路径

典题，每个点只能经过一次，所以只需要设 \(dp[s][j]\) ，s为哪些点已经访问过了状压的状态，j为现在在哪个点，状态转移方程显然

一本通题解

T1：

几种状压dp常见优化方式：
1.先把行内合法情况预处理出来
2.可以用& O(1) 比较两个串的基本情况

T3：

三进制我们先预处理出所有本位合法的情况，再预处理出行间两个状态比较是否合法这样可以优化掉一些复杂度

然后按照三进制存状态和转移即可

状压的精髓就在于，不需要两个状态按位比较，如果两个状态没法 \(O(1)\) 判断是否合法，也就失去了状压的意义

注：写题时，不小心把状态由0开始写成了从1开始，但是竟然拿到了90pts，我当时很惊讶，但是一想，是因为当m！=1时，0状态是不合法的

T4：

我们存一下上两位的状态进行转移，然后枚举第i位，i-1位，i-2位判断合法并转移，转移的话，预处理出本位合法状态和每种状态对应的1的个数即可

观察复杂度，\(2^10=1024\) 你会发现：啊？\(2^{m^3}n\)，跑满的话 \(1e11\) ！

但是你会发现有些情况并不合法，考虑本位合法情况

你可用一个递推来求出合法情况 \(f[i]=f[i-1]+f[i-3]\)

同时也可以采用打表的方式，你会发现，就算所有位置都可以摆炮兵，最多也只有60种合法情况！

最终复杂度 \(O(60^3*100)=O(2e7)\)，轻松跑过

T5：

之前见过相似的trick，但还是没有考虑的很全面

我们考虑只需要通过一个状态的子集转移过来即可，所以对于对于每一种状态暴力枚举子集，具体方法就是 \(j=i\&(j-1)\)，枚举所有的j就是i的子集，然后复杂度是 \(3^n\) 我之前证明过，忘了怎么证了。。。

T6：

先预处理出所有关键点+起点到任意点的距离，然后就很简单了，对关键点跑一遍旅行商问题即可

T7：

考虑设我们经过的点总和s1，边的总和s2，我们最终让s1/s2最小

然后我们考虑一件事情，就是选哪些点确定了，s1就确定了，我们让s2最大化就可以了

所以状压还是存一下选哪些点，然后存的是选这些点能获得的边权最大值，然后注意最开始要将所有状态赋值位-inf，只有起点为0即可，因为这样能保证只能从起点出发

T8：

考虑我们用二进制存一下删掉哪些字母，然后我们就现预处理出每一个字串是否为回文串，然后我们枚举每一种状态，再枚举其子集，转移即可