DP
Lavaloon
·
·
个人记录
区间 DP
P3146 [USACO16OPEN]248 G
定义 f_{l,r} 为 [l,r] 区间能合成的最大数。
于是有状态转移方程：
f_{l,r}=f_{l,k}+1
前提是 f_{l,k}=f_{k+1,r}。
这样 DP 一定是可以得到正确答案的。
复杂度 \mathcal{O(n^3)}。
P3147 [USACO16OPEN]262144 P
观察到最终合成的值顶多 58，故定义 f_{l,k} 代表 [l,f_{l,k}] 区间能合成的最大数为 k。
你看着不顺眼其实是因为我把上一题的值域与定义域中的 r 互换了，所以其实此处的 DP 值就是代表一个右端点。
于是有状态转移方程：
f_{l,k}=f_{{f_{l,k-1}+1},k-1}
其实这个类似倍增。
复杂度 \mathcal{O(nV)}，V 是 58。
P3205 [HNOI2010]合唱队
这个类似于往区间两端塞数进去，由此想到区间 DP。
然而，只记录 f_{l,r} 没法转移，因为你不知道你前面站的比你高还是比你矮。
于是再记录一维表示你前面人的高度？
但是前面那个人一定站在区间的左右端点之一。
具体来讲，记 f_{l,r,0} 表示最终序列 l 最后一个进去，f_{l,r,1} 表示最终序列 r 最后一个进去。
状态转移方程:
f_{l,r,0}=f_{l+1,r,0}(\text{if\ \ } h_l<h_{l+1})+f_{l+1,r,1}(\text{if\ \ } h_l<h_r)
f_{l,r,1}=f_{l,r-1,0}(\text{if\ \ } h_r>h_l)+f_{l,r-1,1}(\text{if\ \ } h_r>h_{l-1})
钦定 f_{i,i,0}=1,f_{i,i,1}=0 ，就是钦定只有一个人时，ta 是从左边进来的。
背包 DP
CF730J Bottles
第一问贪心解决。
那么我们要选几个瓶子已经知道了。
现在我们应该要最大化 k 个瓶子中的水量之和，且这 k 个瓶子能装得下所有水。
定义 f_{i,j,s} 为目前决策完下标 i，已分 j 段，能装得下 s 单位体积的水。
状态转移方程：
f_{i,j,s}=\max(f_{i-1,j,s},f_{i-1,j-1,s-b_i}+a_i)
假如说 s 大于水的总量的话，可以计入答案。
需要滚动数组优化空间。
复杂度：\mathcal{O(n^4)}
状压 DP
P5911 [POI2004]PRZ
序列下标从 0 开始。
定义 f_S 为 S 为 1 的二进制位已经过桥所用时间。
按题意模拟，枚举 S 的子集 T ,有转移：
f_S=\min(f_T+f_{S\oplus T})
另外，S 可以独自过桥。
for(int S=1;S<(1ll<<n);S++)
for(int T=S;T;T=(T-1)&S)
这是枚举子集的简单实现，显然每次都会枚举到一个新的子集，同时不重不漏。
复杂度其实是 \mathcal{O(3^n)} 的。
Proof:
设 S 有 k 位为 1 ，则 S 的子集有 2^k 个。
有 k 位为 1 的 S 有 \mathrm{C_n^k} 个。
复杂度大概是：
\sum_{k=0}^n2^k=\sum_{k=0}^n2^k\times1^{n-k}=3^k
运用了二项式定理。
单调队列优化 DP
CF1077F2 Pictures with Kittens
定义 f_{t,i} 为已选 t 个元素，目前决策完了下标 i 的最大化的元素之和， 钦定 i 被选择。
状态转移方程：
f_{t,i}=a_i+\max_{j\in[i-k,i-1]}{f_{t-1,j}}
单调队列板子。
树形 DP
P3174 [HAOI2009] 毛毛虫
这几乎是树的直径的板子题，然而我没看出来，于是自己推了一个树的直径的树形 DP 的解法：
同时记得合并毛毛虫身上的那些刺。
复杂度 $\mathcal{O(n)}$。
---
### P3574 [POI2014] FAR-FarmCraft
我们发现其实有两类时间：
1. $f_u$ 表示 $u$ 子树最小的内部全部安装完软件的时间；
2. $t_u$ 表示进入到出去 $u$ 子树的时间，显然是等于 $2(siz_u-1)$ 的。
考虑 $u$ 节点和它的儿子们，这个问题变成了一个序列上的问题。
想要最小化 $f_u$ ，只需要表示出 $f_u$ 与子节点的关系，排序贪心即可。
具体地讲，令儿子 $i$ 在儿子 $j$ 前面访问更优，代入 $f_u$ 的计算式，解不等式即可。
最终得到排序依据：对 $t_x-f_x$ 从小到大排序。
向上 DP 即可。
复杂度线性对数。
---
## 树上背包
只做了套路题。
### P1273 有线电视网
发现记录净收入空间会爆。
记录人数，DP 值里面放净收入。
$f_{u,p}$ 表示 $u$ 子树内部选 $p$ 人的最大净收入。
DP 转移方程：
$$f_{u,p}=\max({\sum_{v\in \text{son}_u}}f_{v,q_v})$$
前提是 $\sum q_v=p$。
$\sum q_v=p$ 的限制用辅助 DP 数组处理。
复杂度 $\mathcal{O(n^2)}$。
---
### P1272 重建道路
$n$ 太小，卡不掉 $\mathcal{O(n^3)}$。
$\mathcal{O(n^3)}$ 做法可以枚举哪一个点在大小为 $p$ 的连通块之中，然后强制根节点被选进行 DP。
$f_{u,k}$ 表示 $u$ 子树 __割下去__ 一个大小为 $k$ 的连通块且 __强制包含 $u$ 节点__ 的最少断边次数，注意是 __割掉__ ，而非 __剩下__。
同时，对于割掉整个子树的情况，我们提前考虑一个点和它父亲的连边，即提前计算割掉 $u$ 至 $fa_u$ 的代价。__因此，$f_{u,siz_u}=1$。__
DP 转移方程：
$$f_{u,k}=\min({\sum_{v\in \text{son}_u}}f_{v,t_v})$$
前提是 $\sum t_v=k$。
DP 已经 $\mathcal{O(n)}$ 了，优化寻找答案的过程，即不再进行”枚举哪一个点在大小为 $p$ 的连通块之中“的操作。
若一定包含根节点，则答案为 $f_{1,siz_1-p}$。
若一定包含非根节点，则答案为 $f_{u,siz_u-p}+1$ ，因为你还需要一刀把它从父亲上割下来。
对 $f_{u,siz_u-p}+[i\neq1]$ 取最小值即可。
复杂度 $\mathcal{O(n^2)}$。
---
## 基环树上 DP
### P2607 [ZJOI2008] 骑士 / P1453 城市环路
> 求基环树（森林）最大独立集。
容易对于每个环上的树，求出其最大独立集。
状态转移方程：
$$f_{u,0}=\sum_{v \in \text{son}_u}\max\{f_{v,0},f_{v,1}\}$$
$$f_{u,1}=\sum_{v \in \text{son}_u}{f_{v,0}}$$
然后这就是一个环上最大独立集问题：选了这个点贡献为 $f_{u,1}$ ,不选为 $f_{u,0}$ 。
只需讨论揪出来的环的断点两端选不选即可（环以链的形式存储），中间肯定取最大贡献。
复杂度 $\mathcal{O(n)}$。
---
### P4381 [IOI2008] Island
> 求基环树（森林）直径。
树的直径容易求得，可以采用树形 DP 或 DFS。
具体来讲，树形 DP ： $f_u$ 为 $u$ 子树一端为 $u$ 的最长链，得到答案时合并子节点 DP 值的最大值和次大值。
然后考虑环上怎么做。
先断环为链，$f$ 数组 copy 一遍。
按下标重新编号：$1$ 至环长二倍。
在环上要解决的问题：
> 选出来两个端点 $u,v$ （距离不超过环长），最大化 $f_u+f_v+dis(u,v)$。
$dis$ 数组可以前缀和，记为 $pre$。
现在只需要最大化：$f_u+pre_u+f_v-pre_v$。
记贡献 $w_u=f_u-pre_u$。
最大化 $2f_u+(w_u-w_v)$。
由于有距离限制，考虑单调队列维护。
复杂度 $\mathcal{O(n)}$。