补题进度：5/10
敦敦敦 简单动态规划
温暖的WannaflyCamp End Contest
树形dp
树形依赖背包
题意
给出一棵树，根节点为1，每个点有毒素和收获。要求毒素不超过给定值m的情况下使收获最大。一个点的父亲节点被选取后这个点才能被选取
分析
一个点的父亲节点被选取后这个点才能被选取可以转化为dfs序，从大到小选取，做01背包
下面的i都表示dfs序上的第i个节点
定义
$f[i][j]$：考虑了dfs序>=i所有点的容量为j的最大价值
转移
当$j<c[x]$：$f[i][j] <- f[i+size[i]][j]$ 当$j>=c[x]$: $f[i][j] = max(f[i+1][j-c[x]]+v[x]，f[i+size[i]][j])$
最后的答案即为 $dp[1][m]$
时间复杂度：$O(n·m)$
树的直径
树形dp，待补
当然两遍dfs/bfs也可以求出来
最远点
给定⼀棵带正边权的⽆向树，求每个点的最远点$(n<=10^5)$
分析
待补
树上独立集
题意
给⼀棵树，每个点有点权，求⼀个点权和最⼤的独⽴集$(n<=10^5)$
分析
- f[x] 表示 x 没有选的情况下，以 x 为根的⼦树⾥的最⼤点权和独⽴集
- g[x] 表示 x 选的情况下，以 x 为根的⼦树⾥的最⼤点权和独⽴集
- f[x]=sum(max(f[x],g[x]))
- g[x]=v[x]+sum(f[x])
- 时间复杂度O(n)
区间dp
合并石子
经典的合并石子
定义$dp[i][j]:$ 合并区间[i,j]的最小/最大价值
具体做法：枚举区间长度，区间起点，区间分割点
时间复杂度:$O(n^3)$
2017ICPC(北京) J
题意
n个石子堆排成一排，每次可以将连续的最少L堆，最多R堆石子合并在一起，消耗的代价为要合并的石子总数，求合并成1堆的最小代价，如果无法做到输出0 $(n<=100)$
分析
- 定义dp[i][j][k]：区间[i,j]合并成k堆石子的最小花费
- 转移：你会发现k=1和k>1的转移是由区别
- k=1，dp[i][i+len-1][1]=min(dp[i][i+len-1][1], dp[i][j][k]+dp[j+1][i+len-1][1]+sum[i+len-1]-sum[i-1]);
- k>1，dp[i][i+len-1][k]=min(dp[i][i+len-1][k], dp[i][j][k-1]+dp[j+1][i+len-1][1]);
- Trick：在枚举那两段转移的时候，一定有一个区间1段！！！！！
取数字
题意
给⼀个序列 a[1..n]，每次可以拿⾛连续⼀段满⾜某些条件的数，拿完后序列会并起来
求最少⼏次把整个序列拿完 $(n<=100)$
分析
- 定义f[L][R]表示[L..R]最少⼏次取完
- 考虑 a[L..R]⾥最后取的那⼀段现在是哪些
- 于是把 a 分成了若⼲段，分别做⼦任务
- 复杂度视具体情况⽽定
状压dp
Valley Number II(HDU6149)
题意
- 给定⼀张⽆向图，每个点可能是⾼点或者低点，三个点(x,y,z)被称为⼀个valley当且仅当 x,z 是⾼点，y是低点，且存在边(x,y)和(y,z)
- 现在要求最多有⼏个valley，每个点最多只能在⼀个valley⾥
- N<=30，⾼点数量<=15
分析
- 定义f[i][s]：表示考虑了前i个点，高点的使用情况为s，最多的valley数量
- 转移，枚举低点，对于当前最低点枚举两个高点转移即可
- Trick：滚动数组要把上一层的数先继承过来，再更新
奇怪的道路
题意
- 求有多少⽆向图满⾜有n个点m条边，且每个点度数为偶数，并且对于每条边 (u,v) 都有 1<=|u-v|<=K
- n,m<=30
- K<=8
分析
独⽴集
题意
- 给定⼀张 n 个点的⽆向图，⼩ A 会随机⼀个 [1..n] 的排列，然后按这个排列的顺序来贪⼼选独⽴集
- 求选出来的独⽴集的期望值
- n<=20
分析
数位dp
概率dp
训练题
A
签到
B
题意
题解
C
题意
题解
D
签到
E
题意
题解
待补
考虑每对(i,j)的概率，FFT加速
F
留坑
G
对于每个$w_i$考虑每个位置的算的次数，可以发现不断枚举L,R，前缀和序列$a_i$，算出贡献即可
H
题意
题解
结论：同一高度黑色都为偶数个先手输，反之先手赢
证明：
I
分为两种情况即可
- 根选的话，考虑每个子树选的数量
- 根不选，考虑每个子树内部的组合方案
J
复读机模拟