状压DP大楼

admin

一般的DP在转移方程的时候，
这也是一种多维变一维的技巧
前期知识： 位运算
典型例题：
1、P1879玉米地  http://hsyit.cn/forum.php?mod=viewthread&tid=36304
2、1*2骨牌覆盖  http://hsyit.cn/forum.php?mod=viewthread&tid=22
3、P1123 选数  http://hsyit.cn/forum.php?mod=viewthread&tid=35882
4、P2704 [NOI2001]炮兵阵地   http://hsyit.cn/forum.php?mod=viewthread&tid=36308
5、P1896 [SCOI2005]互不侵犯  http://hsyit.cn/forum.php?mod=viewthread&tid=36319
6、P2622 关灯问题II http://www.hsyit.cn/forum.php?mod=viewthread&tid=36325

admin

前期知识1：位运算前期知识2：杨辉三角，数字三角形。体会本行和上一行的关系

admin

思考题1：n个点的有向图，给出距离的邻接矩阵，求经过每个点一次的最短路径。n<=20
思考题2：给出一些城市和连接它们的双向边，无重边，无自环，通过道路需要车票，你有n张车票，每张车票都有一个值，只能使用一次，通过i号道路使用j号车票所用时间是di/tj。询问从城市a到b的最短时间，无解输出Impossible。n<=10,点数<=30,边数<=2000  POJ2686

思考题3：平面上有N个点，现在要用一些矩形（各边都在格线上）来覆盖它们，每个矩形至少覆盖2个点，求最少的矩形总面积n<=15 预处理将n个点两两组合形成n * (n-1) / 2个矩形 d(S)表示点集为S时的最小面积c[i]为矩形内的点，m[i]为矩形面积
题意 ：给出N个字符串，寻找一个字符串使得这N个字符串都是它的子串。输出最短的满足要求的串，如果有多个最短，输出字典序最小的
len<=100
n<=15
5s POJ1795

题意：N个城市间有m条单向路，分别从a到b，可以在c处交P路费（只能预交，不能赊账），也可以直接交R路费。无法到达输出impossible
n<=10

admin

在n*n(n≤20)的方格棋盘上放置 n 个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。

给出一个 n*m 的棋盘(n 、m≤ 80,n*m ≤ 80)，要在棋盘上放 k(k ≤ 20)个棋子， 使得任意两个棋子不相邻。问有多少种方案。

推荐练习：poj 1185      hdu1074    poj 3254   poj3311   hdu3001   poj 2288   zoj  4257   poj 2411   hdu 3681.

admin

归纳总结一下吧，不然学了就忘
目前接触过四种题型，

1、问图的布置方案数（母牛，铺砖，摆放棋子）
dp[ i ][ state ] = sigma( dp[i-1] [ stateB ] )

2、问图中元素的最大拜访个数（炮兵阵地）
dp [state] = max( dp[i-1] [stateB ]) 遍历i-1的stateB

3、操作一系列事件得到的最值
state 可以推出 nstate
dp[ nstate ] = max( dp[nstate] , dp[state] + 代价) , 从当前state可以逐个分析已经获得的信息。

4、图的哈密顿路径（从起点出发，每个点恰好路过一次，限定一些路径，求最小代价）
dp[ state ] [ u ] 表示已完成的图的状态，已经当前点在u上 的最小代价
倘若 u -> v
dp [ state | (1 < < v) ][ v ] = max ( dp [ state | (1 < < v) ] [v], dp[ state ] + mp[ [v] )
————————————————
版权声明：本文为CSDN博主「2112222222222」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37591656/java/article/details/81903651

admin

题意： 给你n条长度m的序列， 现在在m里面选择搭配任意的m子序列，问n条序列在某种搭配下，不相同的序列个数大于k 的搭配数。
思路：让state表示选中的子序列。很显然我们要遍历 (1 << m)次状态。我们用DP[ state ] [ i ]记录当前搭配状态下，前i行有几种不同的序列，那么递推方程就是 dp[ state ][ i ] = dp[ state ] [ i-1 ] + i - 1 + X ； 是什么鬼？ X代表前i行中，规定了搭配方案后，得到的序列出现的次数。 加上 i - 1 再减去 i 行在state 下的状态出现的次数，就得到了前i行不同序列的个数。
————————————————
版权声明：本文为CSDN博主「2112222222222」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37591656/java/article/details/81903651

admin

5、ZOJ3777B - Problem Arrangement
秒啊，题目开始越来越不裸了

题意：给出矩阵mp[ n ][ n ] ， 如果mp[ i ][ j ] 选中，那么 i 行 j 列就不能选了 ，求选中的n 个点权值之和大于 k 的选法。
思路：分析题目，往常的dp都和当前行状态相关，则需要开一维保存行信息。 本题由于每行只选一个每列只选一个，那么state就能记录下当前状态已经存在几行。我们让dp[ state ][ val ] 列上的被选中的状态state ， 得到的价值val。那么答案就是 dp[ (1 << n) - 1] [ m ] ，本题用刷表法， 为什么不用填表法呢？ 填表法需要从上一个状态推到当前的状态，也就是说我们要知道上一行的状态 ，我们很难知道 state 对应在 i 行的 具体是哪一列 ， 也就无法 在 已知当前行的state ，推出哪些state是属于上一行。 刷表法就比较容易推， 我们可以由state 定位到当前是第几行，然后再找出当前可能的val值 ， 通过当前的state 和 val 就能推出下一个 state | (1 << j ) 、val + mp[ i ][ j ] 。说的有点乱，总之先思考一下刷表还是填表。
————————————————
版权声明：本文为CSDN博主「2112222222222」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37591656/java/article/details/81903651