令人崩溃的状压dp

来自上海交大的柳哥哥，今天给我们讲了状压dp，真的很难听懂啊~~

▪在DP进行状态表示的时候，总会遇到一些只使用f [ i ] [ j ] 无法表示的状态。

▪例如：用 DP方法解决TSP 问题

▪这里设置的状态中需要记录下来前面已经走过的城市，所以需要一种方便简洁的手段来表示此信息。

所以，状态压缩dp就要补充一点位运算了：

 

▪<< 左移

▪>> 右移

▪& 与

▪|   或

▪~ 非

我们所需要做的是

▪以位运算来记录下来所有城市中哪些城市走了，哪些城市没走。

▪例如 二进制数(10010) 表示第2个，第5个城市已经经过，其他城市未经过。

这里要先学一些组合的操作：

▪（1<<( i  ) ）等价于 2^i

▪x | ( （1<<( i  ) ） )  将 x 的第 i+1 位强行变成 1

▪if ( x & (1 << ( i - 1 )  )  ) 检测x的第 i 位是否为 1

▪for( int i = S  ;  i ;  i =(i-1)&S ) 枚举子集

▪-x 等价于(~x)+1   (x&-x) 只保留x 的最后一位

^ 异或

证明过程，可以有兴趣上网搜索，有空，我也会更新贴上~

————————————————————2019.1.27第一次更新——————————————————————————

————————————————————已经经历一次更新————————————————————————————

例题1 ：求解TSP问题

▪有n个城市，从起点 0 开始游历每一个城市，只访问每个城市一次，最后回到起点，所需要的最短路径是多少？

▪n<=15

这题，n很小，老师也跟我讲，他选择了状压dp

▪设 f [ i ] [ S ] 表示当前在 i 点处 ， 已经经过的城市信息 用 S保存 的最短路径。

▪假设 用 c [ i ] [ j ] 表示一条 从 i 点到 j 点的有向边。

▪ 则

▪

▪用 f [ i ] [ S ] 更新 f [ j ] [ S | ( 1 << j - 1 ) ]

 

例题2 关灯问题

▪现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——

▪按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于

▪第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开

▪了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是

▪关的，那么把它打开，否则也不管；如果是0，无论这灯是否开，

▪都不管。

▪现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问

▪最少要按几下按钮才能全部关掉。

▪n<=15,m<=100

 

▪设 f [ S ] 表示从初始状态到达 S 状态的最小步数。

▪具体操作类似 B F S 。

例题3

例题3

▪农场主John新买了一块长方形的新牧场，这块牧场被划分成M行

▪N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。

▪John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

▪遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜

▪欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也

▪就是说，没有哪两块草地有公共边。

▪John想知道，如果不考虑草地的总块数，那么，一共有多少种种

▪植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

 

▪假如上一行是确定的，我们就可以判断下一行是否合法。

▪所以设 f [ i ] [ S ] 表示第 i 行状态为 S 时的方案数。

▪转移时，枚举上下两行，复杂度较高。

 

 

 

例题4：NOIP 2017 宝藏

▪给出一副无向图,每条边都有一个权值且均未开通,先可以随便取一

▪个起点,要开通一些边,使它成为一个连通图,开通一条边的代价为

▪这条边的权值*起点到它的点的个数(起点也算),求最小代价.

▪边数m<=1000

▪点数

–70% n<=8

–100% n<=12

▪关键点是考虑如何划分阶段。

▪方案1：枚举起点，用S记录树的形态，树形态总数为2^28级别(n=8)

▪方案2：考虑以每次选择一条新开通的边为阶段，那么对于每个节点，我要记录当前第 i 个节点与起点的距离。

▪考虑70%数据情况下，状态总数为8^8级别，可做。

▪设f [ S ] 表示当前节点与起点的距离为状态为S的情况下的最小花费。 这里 S 需要使用 8 进制压缩。

 

▪方案3：考虑每次集中处理所有与起点距离为 k 的节点。

▪设 f [ i ] [ S ]表示处理到了与起点距离为 i 的节点，已经与起点相连通的节点集合 为 S 的最小花费。

▪每次枚举所有不在S中的点构成的集合S'作为第 i+1层。

▪状态转移方程为：

▪

▪把S集合和S' 集合相连的最小的距离是另外一个DP。

 

 

关于一些优化

▪状压DP用递推写的一个通病是会访问大量的无效状态。

▪这时候记忆化搜索会显得非常优秀。

 

以上讲析均来自柳哥哥（993124494）