DP设状态 : 状压与线

[NOIP2017]宝藏(状压)

[AHOI2009]中国象棋(状压)

[BZOJ1814] URAL1519 Formula 1(插头\(DP\)模板)

新链接 : Luogu5056 , darkbzoj1814
代码借鉴 : Icefox

[BZOJ1187] HNOI2007 神奇游乐园(插头\(DP\))

Luogu3190
由找方案数变成了找最大值

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]\)为最终的方案

巴特西

DP设状态 : 状压与线

最新文章

热门文章