集合型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][]$$

树形DP

二叉苹果树


思路

  • $dp[u][j表示节点u留下j条边的最大价值,每一次决策只有三种情况:剪左子树,剪右子树,两个都不剪
  • 剪左边:$dp[u][j]=dp[rson][j-1]+v[rson]$,同理,剪右边:$dp[u][j]=dp[lson][j-1]+v[lson]$
  • 两边都不剪:$dp[u][j]=dp[lson][j]+dp[rson][k-j-2]$

代码:记忆化搜索

int f[N][N];
bool t[N][N];
int dp(int u,int k)
{
if(t[u][k]) return f[u][k];
t[u][k]=1;
if(!k) return f[u][k]=0;
int tmp1=dp(lson[u],k-1)+v[sonl[u]];
int tmp2=dp(rson[u],k-1)+v[sonr[u]];
int tmp3=0;
for(int l=0;l<k-2;l++)
tmp3=max(tmp3,dp(lson[u],l)+dp(rson[u],k-l-2));
return f[u][k]=max(tmp1,max(tmp2,tmp3+lson[u]+rson[u]));
}
Your browser is out-of-date!

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

×