集合型DP

集合型动态规划

如何用一个数表示集合?

bitset:用一个二进制数

$\cup$:s1 | s2
$\cap$:s1 & s2

查询是否有第i位:(1<<i) & s

补集:((1<<n)-1) ^ s

基环数DP

基环树DP:一个数加一条边

骑士


题目

有n个骑士,每个骑士痛恨另一个骑士,每一个骑士拥有一个战斗力值。选出一个战斗力最强的军团,军团中没有骑士痛恨另一个骑士。

思路

  • $dp[u][0],dp[u][1]$分别表示u取或者v取,然后就可以剪断那条边,变成树形DP

期望DP

麻球繁衍


题目

有k只麻球,每只活一天就会死亡。每只麻球临死前会生出新的麻球,生i只麻球的概率为Pi。求m天以后所有麻球都死亡的概率

思路

  • 考虑一只麻球
  • $f(i)=P_0+P_1f(i-1)+P_2f^2(i-1)+……+P_{n-1}f^{n-1}(i-1)$
  • 最终答案为$f^k(m)$

得到

思路

  • $f(x)=1+\frac{1}{c}$

抢掠计划

数位DP

数位DP

不要62


分析

  • $dp[pos][state][limit]$ 表示当前枚举到第pos位,前几位的状态为state,前几位有无limit限制时符合条件的数字的个数
  • $$dp[pos][state][limit]=dp[pos-1][]$$

lowbit函数

lowbit函数

lowbit(10010)=10

lowbit(10010001)=1

lowbit(100100000)=100000

正数的原码、补码都是它自己

负数(-5为例):

原码:10000100

反码:111110110

补码:111110111

lowbit(x)=x&(-x)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×