[NOIP2017]宝藏(状压)
[AHOI2009]中国象棋(状压)
[BZOJ1814] URAL1519 Formula 1(插头\(DP\)模板)
新链接 : Luogu5056 , darkbzoj1814
代码借鉴 : Icefox
[BZOJ1187] HNOI2007 神奇游乐园(插头\(DP\))
Luogu3190
由找方案数变成了找最大值
[HDU1693] Eat the Trees(插头\(DP\))
Luogu5074
求闭合方案数
设 \(f[i][j][k]\) 表示做完第 \(i\) 行 , 第 \(j\) 列 , 目前那 \(m+1\) 个插头的选取二进制状态为 \(k\) 的方案数 .
初始值 : \(f[0][m][0]=1\)
每行继承值 : \(f[i][0][k<<1]=f[i?1][m][k] , k∈ [0,2m)\)
因为上一行最后一个位置不能有未闭合的插头！
转移 : 若位置 \((i,j)\) 有障碍 , 则看能否从前一格继承过来 , 不能就只能是\(0\)了 .
若无障碍 , 则肯定有转移 : \(f[i][j][k]+=f[i][j?1][k\bigoplus(1<<(j-1))\bigoplus(1<<j)]\)
如果符合条件 , 还能继承结果 : \(f[i][j][k]+=f[i][j?1][k]\)
答案 : \(f[n][m][0]\)
[SCOI2011]地板(插头\(DP\))
分六种情况讨论 , 详见原题解
[九省联考2018]一双木棋(轮廓线&搜索)
这题的搜索做法是对每一个状态\(hsah\)存下答案
轮廓线做法 : 用 \(1\) 表示竖着的轮廓边 , \(0\) 表示横着的轮廓边
然后可以发现 , 状态的转移就是把其中一个 \(1\) 向左挪一个位置即可 \(01?>10\)
然后发现转移的顺序不太明显 , 所以用记忆化搜索? , 反过来写便于理解一些
[ZJOI2007]棋盘制作(悬线法)
[WC2008]游览计划(斯坦纳树)
[JLOI2015]管道连接(斯坦纳树)
[FJOI2017]矩阵填数(扫描线)
\(1.\)离散化出每一块内部不互相影响的块
\(2.\)\(dp[i][j]\)为前 \(i\) 种重叠块其中有 \(j\) 这些状态的矩阵的最大值被满足了的方案数 , 这样转移就之和这个块有关了 , 直接计算取最大值和不取的方案数即可
则当取最大值时，把对应方案数转移到 \(dp[i + 1][j | s[i + 1]]\)，否则转移到 \(dp[i + 1][j]\)
故 \(dp[Bcnt][(1 << n) - 1]\)为最终的方案
原文：https://www.cnblogs.com/lizehon/p/10630780.html