警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「笔记」day3 - DP

:warning:注意:这是ZROI集训的源笔记,其中有很多缺失和遗漏以及无法看懂的部分,大家就不要看了吧。

以下是原笔记:


day2 欠账

最长简单环

\(f_{p,s,t}\)\(s\)\(t\)经过点集\(p\)是否存在。

初始:\(f_{2^{i-1},i,i}=1\)

如果\(i\)满足\((t, i) \in E, (p>>(i+1)\&1)=0\),就可以转移\(f_{p|(1<<(i-1)),s,i}\)

\(f_{p,s,t}=1\)\((t,s) \in E\),则长度为__builtin_popcount(p)

复杂度:\(2^nn^3\)

优化

限定\(s\)是环中最小的编号,其它条件不变。

转移时枚举\(s+1...n\)

\(\sum_i^n2^nn=n\sum_{i=1}^n2^i=O(2^nn)\)

例题6

\(f_p\)在组里的最大收益。

\(f_p=\max\limits_s w[s]+f_{p-s}\)

\((p\&s)=s\)

\(O(4^n)\)并不能跑过\(n=16\)

优化

\(p\)\(2^{k-1}\)个非空子集,可以用\(0\)~\(2^{k-1}\)表示所有的子集。只需\(2^{k-1}\)枚举子集。

对于每一个集合\(P\),那么子集数为\(2^{|P|}\)

复杂度\(O(3^n)\)

1
2
3
for (s=p; s; s=(s-1)&p) { // 不重复枚举所有p的子集 
// do something...
}

生成树计数

\(1\)为根。

\(f_{i,p}\)代表\(i\)的子树中,有\(p\)个点的子树个数。

1
init :	f[i][1<<(i-1)] = 1;

\(f_{i,p}=\sum f_{j,s}f_{i,p-s}, s\subseteq P-\{i\} , j\in s\)

\(\min(P-\{i\})=k\)

复杂度\(O(3^nn^2)\)

枚举顺序

i 1~n

P 0~2^n-1

斯坦纳树

\(f_{i,p}\)\(i\)为根,经过关键点集合\(p\)

  1. \(i,j\)是关键点\(f_{i,p}=\min f_{j,s}+f_{i,p-s}+w_{i,j}\)
  2. 孤立点从子树接边\(f_{i,p}=\min f_{j,p}+w_{i,j}\)

带环,需要用最短路转移!

轮廓线DP\(\subseteq\)状压

例题9

暴力

\(f_{i,p}\)代表扫到了\(i\)列,\(p\)从上一行突出来了。

Procedure:

  1. \(p\)碰到障碍点,直接扔掉。

  2. 枚举\(s\),代表在第\(i\)行会横出下一行。

满足s&(p|障碍)=0

而且竖着的骨牌必须可以摆在~(s|障碍|p)中。

复杂度\(3^nn^{很多次方}\)

高端操作(轮廓线DP)

首先一列一列放骨牌,然后总共有\(n+1\)个边界。

放置的方式:

1
2
3
4
5
6
7
1 8 15 . #
2 9 . . #
3 10. . #
4 11. #
5 12. #
6 13. #
7 14. #

边界:

1
2
3
4
5
6
7
. . . . # 1
. . . . # 1
. . . . # 1
. . . # 2
. . . # 1
. . . # 1
. . . # 1

如图,有\(n+1\)个边界。

可以记录状态\(f_{i,j,p}\)代表放到了\((i,j)\)点,边界\(p\)方案数。

不合法状态:

  • \(i\)要长出来或\(i+1\)要长出来并且\((i,j)\)是障碍。
  • \(i\)\(i+1\)都要长出来。

合法状态:

  • \(i\)\(i+1\)只有一个长出来并且\((i,j)\)不是障碍,

转移到\(P-(1<<(i-1))\)\(P-(1<<i)\)

  • 其它长出情况直接转移到\(P+(1<<(i-1))\)\(P+(1<<i)\)

最后扫完一行后需要更新轮廓线才可以继续DP。

  • 新的轮廓线中的第一个一定是\(0\)(边界外不可能有股牌下来)
  • 如果\(n+1\)\(1\)就直接丢掉(伸到了边界外面)
  • 然后就直接左移一位(\(1\)移到\(2\) \(2\)移到\(3\)...\(n\)移到\(n+1\))

复杂度\(O(2^nn^2)\)

枚举顺序\(j\)\(i\)\(p\)

k国王问题

\(f_{i,j,k,p}\)

放到\((i,j)\),放了\(k\)个国王,轮廓线外的\(p\)格会被攻击。

讨论两种情况:放还是不放。

放就把周围一圈的\(p\)更新,否则直接转移。

\(\max\limits_i=0\)

day2e

B

\(f_{叶子}=+\inf,f_.=0\)

\(f_i+=\min(w,f_j)\)

C

\(f_{i,p}\)\(i\)\(p\)是否能到达

枚举\(a\)\(b\)

\(f_{i,p}->f_{i+1,p+(1<<(a-1))+(1<<(b-1))}\)

\((p>>(a,b-1))\&1=0\),满足边

A

\(f_{i,j}=\sum_{k=0}^{w_i}f_{i-1,j-k}\binom jk\)

\(O((\sum w_i)^2)\)

D

改板轮廓线DP模板

E

\(f_{i,j}\)深度\(\le j\),有\(i\)点。

\(f_{i-1,j-1}\cdot 2\cdot i\)

\(\sum_{k=1}^{i-2}f_{k,j-1}\cdot f_{i-k-1,j-1}\cdot i\cdot \binom{i-2}{i-k-2}\)

\(f_{0,i}=1\)

\(f_{1,i}=1\)

状态\(O(nd)\),转移\(O(n)\)

复杂度\(O(n^2d)\)