Part 1 排列 DP

1. AT_dp_t Permutation / UVA1650 数字串 Number String

实际上，对于 $1 \sim 6$ 的一个排列，如果 1 2 6 5 4 3 是合法的，那么 1 3 8 6 7 5 也是合法的。

也就是说，题目并不关心这几个数是否真的是 $1 \sim 6$ 的一个排列，所以可以考虑不考虑这些数值的实际大小，而是关心他们相对的排名。

设 $f_{i, j}$ 表示处理好前 $i$ 个位置，其中第 $i$ 个位置放在这 $i$ 个数中排名为 $j$ 的数。

如果这一位需要比前一位大（这一位是 $<$ ），那么：

f_{i, j} = \sum_{k = 1}^{j - 1} f_{i - 1, k}

如果这一位需要比前一位小（这一位是 $>$ ），那么：

f_{i, j} = \sum_{k = j}^{i - 1} f_{i - 1, k}

2. AT_abc209_f [ABC209F] Deforestation

先讨论什么时候价值最小：

先砍 $i$ ，再砍 $i + 1$ ，代价是 $a_{i - 1} + a_{i} + a_{i + 1} + a_{i + 1} + a_{i + 2}$ 。
先砍 $i + 1$ ，再砍 $i$ ，代价是 $a_{i} + a_{i + 1} + a_{i + 2} + a_{i - 1} + a_{i}$ 。
上减下得 $a_{i + 1} - a_{i}$ 。
也就是说，当 $a_{i} < a_{i + 1}$ 时，先砍 $i$ 最优；当 $a_{i} > a_{i + 1}$ 时，先砍 $i + 1$ 最优。

题目变为有多少种排列 $p$ ， $\forall i$ ， $a_{p_{i}} < a_{p_{i + 1}}$ 。

上一题改改即可。

3. 【重点】P5999 [CEOI2016] kangaroo

从另一种角度看排列 DP，这一角度下排列 DP 通常的设法是：设 $f_{i, j}$ 表示前 $i$ 个数组成了 $j$ 段答案的方案数，答案即为 $f_{n, 1}$ 。

状态是什么意思呢？比如对于上面 T1，现在求出三部分答案区间： $(1)$ ， $(5, 3)$ ， $(2, 4)$ ，这些区间内部都必须满足答案要求的性质。这就是 $f_{5, 3}$ 包含的一种方案。

对于这样的状态，一般有三种操作：

随便挑一段区间将第 $i$ 个数接到它的结尾：

f_{i, j} = f_{i - 1, j} \times j

自己开一段区间，由于这一段区间可能插在上一个状态的 $j - 1$ 段形成的 $j$ 个空（包含序列两端也可以插入）中的任意一个空中，所以：

f_{i, j} = f_{i - 1, j - 1} \times j

合并左区间和右区间，自己放到中间，上一个状态的 $j + 1$ 段只有 $j$ 个“中间”（序列两端的，显然不能合并），所以：

f_{i, j} = f_{i - 1, j + 1} \times j

回到这一题。这道题的本质是求上面 T1 中的 $>< \dots ><$ 序列和 $<> \dots <>$ 序列的总方案数，只不过固定了开头数和结尾数。

用同样的方法设状态，从小到大考虑插入每一个数。

不存在第一种操作，因为从小到大考虑，要是个个数都直接往前面序列的后面接，必然会形成一个完全单调递增的“答案序列”，和题意不符。
第二种操作必然合法，它新开一段区间，前后都没有数，没有大于小于的比较。
第三种操作必然合法，因为从小到大考虑，现在考虑的数肯定比之前的数都要大，把自己放到中间合并任意两个区间，都能构成以自己为中心的 $<>$ 。
对于起点，它的操作二只有插在序列开头一种方案，所以 $f_{i, j} = f_{i - 1, j - 1}$ 即可，不用 $\times j$ 。它的

4. 摆花

5. 数列

6. CF1806D DSU Master

7. P9197 JOI Open 2016 摩天大楼

8. CF1437F Emotional Fisherman

9. CF1439D INOI Final Contests

10. AT_agc030_f [AGC030F] Permutation and Minimum_

11. P7213 [JOISC2020] 最古の遺跡 3

Part 2 线性 DP

1. AT_abc281_g [ABC281G] Farthest City

2. CF1476F Lanterns

3. AT_agc035_e [AGC035E] Develop

Part 3 树形 DP

1. P6383 『MdOI R2』Resurrection

对上脑电波了（喜，可能是这题比较简单。

说句闲话，我语文素养较低，导致我看题意看了半天。

首先，对于“从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点”，即从 $u$ 往 $n$ 节点编号单调递增，就可以想到把 $n$ 当作原树的根，有 $\forall d e p_{u} < d e p_{v}, u > v$ 。

接着画图想它的断边操作，可以发现新树中，某个节点的父亲一定是原树中的祖先，因为如果从 $x$ 节点往下拐得到 $y$ 是最大的，那就违背了上一行的规律。

所以问题就变成了：以 $n$ 为根，随便将一些节点往上挂，能够得到多少种新树。

但是“随便”是不够的，会发现样例都过不了，其实还有个条件：每个节点在新树中的深度，都必须大于等于他原树中其中一个祖先，在新树上的深度。

其实原因也很显然：凭什么这个节点能连到上面去而它没一个祖先能连上去……

因此设 dp 状态 $f_{u, i}$ 表示只考虑 $u$ 及其子树，最小只向深度为 $i$ 的祖先连边的方案数，则有 $f_{u, i} = \prod \sum_{j \geq i} f_{v, j}$ 。

最后将答案合并进 $f_{n, 0}$ 即可。前缀和优化为 $O (n^{2})$ 。

2. P10789 [NOI2024] 登山

3. CF1799H Tree Cutting

Part 4 状压 DP

1. P8292 [省选联考 2022] 卡牌

如果质数个数较小，只需大力容斥即可，用总方案减去所有不合法的方案：钦定覆盖 $0$ 个质数 $-$ 钦定覆盖 $1$ 个质数 $+$ 钦定覆盖 $2$ 个质数……

但是质数个数很多，但又不算多，根据 NOI2015 寿司题经验，可以发现 $43 \times 47 > 2000$ ，也就是说每一个数最多只有一个大于 $43$ 的质数，所以考虑根号分治。

考虑只有大质数怎么做，那么直接枚举给出的卡牌序列里整除大质数 $p$ 的个数 $f_{p}$ ，然后如果要求被大质数 $p$ 整除，那么这 $f_{p}$ 个卡牌不能全不选， $2^{f_{p}} - 1$ ，否则就放养， $2^{f_{p}}$ 。

接下来只需要把第一段和第三段结合起来，即对每种不同的小质数集合都算一次大质数的答案，容斥即可。

Part 1 排列 DP ​

1. AT_dp_t Permutation / UVA1650 数字串 Number String ​

2. AT_abc209_f [ABC209F] Deforestation ​

3. 【重点】P5999 [CEOI2016] kangaroo ​

4. 摆花 ​

5. 数列 ​

6. CF1806D DSU Master ​

7. P9197 JOI Open 2016 摩天大楼 ​

8. CF1437F Emotional Fisherman ​

9. CF1439D INOI Final Contests ​

10. AT_agc030_f [AGC030F] Permutation and Minimum_ ​

11. P7213 [JOISC2020] 最古の遺跡 3 ​

Part 2 线性 DP ​

1. AT_abc281_g [ABC281G] Farthest City ​

2. CF1476F Lanterns ​

3. AT_agc035_e [AGC035E] Develop ​

Part 3 树形 DP ​

1. P6383 『MdOI R2』Resurrection ​

2. P10789 [NOI2024] 登山 ​

3. CF1799H Tree Cutting ​

Part 4 状压 DP ​

1. P8292 [省选联考 2022] 卡牌 ​

2. CF1842H Tenzing and Random Real Numbers ​