板刷 DP

前言

由于自己 DP 太菜了，因此打算板刷一波（？

不知道能坚持多久，尽量搞下去吧。

存几个题单（不分先后）：

• 【动态规划】普及~省选的dp题
• codeforces 2000左右的dp题
• codeforces 2100左右的dp题
• Educational DP Contest (AtCoder)

20220618

CF66E Petya and Post

环形 DP。

从顺逆时针分别考虑，假设 \({dp}_i\) 表示从 \(i\) 出发整个过程中油量最小值，预处理出一个值然后递推即可。

递推式为 \({dp}_i={dp}_{i+1}+a_i-b_i\)，另一方向同理，复杂度 \(\mathcal O(n)\)。

P3914 染色计数

树形 DP。

容易得到一个 \(\mathcal O(n^3)\) 做法（\(n,m\) 同阶），即设 \({dp}_{i,j}\) 表示考虑 \(i\) 子树内，\(i\) 号点颜色为 \(j\) 的方案数，然后暴力枚举所有儿子颜色，根据乘法原理进行转移。

设 \({sum}_i=\sum\limits_{j=1}^m{dp}_{i,j}\)，就可以省下暴力枚举儿子颜色部分的复杂度，降为 \(\mathcal O(n^2)\)（\(n,m\) 同阶）。

AT4537 Independent Set

树形 DP。

设 \({dp}_{i,0/1}\) 表示考虑 \(i\) 子树内，\(i\) 号点是白色还是黑色的方案数，根据乘法原理进行转移，复杂度 \(\mathcal O(n)\)。

CF455A Boredom

线性 DP。

设 \({dp}_i\) 表示在 \(1\sim i\) 选择若干个数的最大价值，则 \({dp}_i=\max\{{dp}_{i-1},{dp}_{i-2}+i\cdot {cnt}_i\}\)，其中 \({cnt}_i\) 是 \(i\) 的出现次数，复杂度 \(\mathcal O(n)\)（\(n,w\) 同阶）。

20220621

先记在这里，过两天补。

https://hydro.ac/d/bzoj/p/1688 和 https://www.luogu.com.cn/problem/P2135 & https://www.luogu.com.cn/problem/UVA10559 的双倍经验。