SYC2022 Day2 动态规划

Example 1. [Topcoder SRM 713 Medium] DFS Count

给一个图, 求不同的 DFS 序个数。$n ≤ 18$。

DFS 序的性质是：一旦进入一个点，就一定会把它能到达的所有点（且不经过已达点）都遍历到再退出。

设 $g_{S,u}$ 表示不经过点集 $S$ 的 $u$ 的可达点集，再设 $f_{S,u}$ 表示从 $u$ 出发进入点集 $S$ 的方案数；转移 $f$ 时就枚举第一步向哪个子节点走即可。

Example 2. [CF868E] Policeman and a Tree

$n$ 个点的树, 有一个警察初始在 $s$ 点, 移动速度为 $1$；$m$ 个小偷在 $x_i$ 点, 移动速度为无穷大。如果警察和小偷某个时刻在同一地点, 小偷就会被抓住. 求最坏情况下警察抓住小偷需要的最少时间。$n, m ≤ 50$。

难点在于状态的设置。我们发现当警察正在某条边上的时候，小偷的状态只取决于边的两端的两棵子树分别有多少小偷。设 $f_{e,a,b}$ 表示正在经过有向边 $e$ 且两边各有 $a,b$ 条边时的最小剩余时间，转移时就是一个背包问题。

Example 3. [CF762E] Tree Nesting

给两棵树 $S,T$ 问 $S$ 有多少个子图与 $T$ 同构。$|S| ≤ 1000, |T| ≤ 12$。

枚举 $T$ 在 $S$ 中深度最浅的点是哪个，视其为 $T$ 的树根（如果有有根树同构的情况需要去掉）。然后在 $S$ 上 dp：设 $f_{u,v}$ 表示 $S$ 中的 $u$ 子树与 $T$ 中的 $v$ 子树匹配的方案数。转移时发现其实就是要填满在 $T$ 中的每个儿子，用一个状压 dp 就可以完成转移（记得最后要除以 $T$ 中 $v$ 的子树中树同构的可重排列数）。

Example 4. [LOJ2292] Score List

有 $n$ 个数 $a_i$，你每次可以消掉一个区间，其基础代价为 $a$，额外代价为 $b$ 乘这些数的极差的平方。消掉之后，两边会拼在一起。求最小代价。$n ≤ 50$。

设 $f_{i,j,l,r}$ 表示区间 $[i,j]$ 内消到只剩区间 $[l,r]$ 以内的数的最小代价，$g_{i,j}$ 表示完全消除 $[i,j]$ 区间的代价。转移方程有：

状态设置上非常巧妙，并且第一个转移方程实际上基于一定性质。

Example 5. [LOJ6240] Cactus

求对一个仙人掌随机点分治复杂度的期望。$n\le 400$。

复杂度即为 $\sum size_u$（$size$ 为点分树上 $u$ 点子树的大小）。根据期望的线性性，我们只需求出 $i$ 被删除时 $i,j$ 联通的概率的和即可。而 $i,j$ 连通相当于 $i$ 点在路径 $i\rightarrow j$ 上是第一个被删除的。枚举并容斥计算这个概率的和即可。

Example 6. [AGC016f] Games on DAG

给一个 $n$ 个点的 DAG, 求有多少个边的子集使得新图上 $SG(1) \not= SG(2)$。$n ≤ 15$。

设 $f_{i,S}$ 表示集合 $S$ 内的点都有连边向所有 $\{0,1,2,\cdots,i-1\}$ 的当前方案数。枚举集合 $T$ 表示集合 $T$ 内的点的 $SG$ 值为 $i$，那么 $T$ 集合内的边得到了固定（都不能有），$S-T$ 内的点每个点的连向 $T$ 的出边中至少有一个是选中的，直接 $\prod 2^{deg_u'}-1$ 即可计算系数。

我们惊奇地发现，其实 $i$ 这一维根本不重要！所以直接设 $f_S$ 表示导出子图 $S$ 上的……的方案数，然后转移等是一样的。$O(3^n)$。

Example 7. [300iq Contest 3H] Horrible Cycles

给一个 $2n$ 个点的二分图, 左边第 $i$ 个点向右边前 $a_i$ 个点连边, 求图中的简单环个数。$n ≤ 5000$。

简单环个数，$n$ 较大，这个就让人联想到线头 dp 了；但我们可能需要一个合理的转移顺序。

我们把所有点按照某种方式排序，使得每个左部点都可以向它左边所有右部点连边。经过手玩，我们发现在某个 $i$ 左边的所有选中的连边构成若干线段，这些线段都以右部点为两端点；新加入一个右部点相当于新建一个线段；加入一个左部点则会合并两个线段。设 $f_{i,j}$ 表示 $i$ 左边有 $j$ 条线段的方案数，$O(n^2)$ 转移。

Example 8. [Atcoder?] Unicyclic Graph Counting

求 $n$ 个点的基环树个数，满足第 $i$ 个点的度数为 $d_i$。$n ≤ 10^5$。

我们定义基环树的 prufer 序列：

每次删除其编号最小的儿子，并记录其父亲的编号，直到只剩下环为止。

但是这种 prufer 并不能很好地表示环上每个点之间的位置关系，所以还需要乘上一个环排列。记 $f_{i,j}$ 表示前 $i$ 个点、环大小为 $j$ 的方案数，转移时就讨论 $i$ 号点是不是环上的点即可。但是这样还有一点问题：我们发现这个 prufer 序列的结尾必须是环上的点。因此我们再记一维 0/1 表示是否已经钦定了这个最后的点（必然在环上）。

可以使用分治 FFT 优化转移。

Example 9. [300iq Contest 1J] Jealous Split

给一个长度为 $n$ 的序列，将其划分为 $k$ 部分，记 $s_i$ 表示第 $i$ 部分的和，$m_i$ 表示第 $i$ 部分的最大值，构造这样一个划分使得：$∀1 ≤ i < k$，$|s_i − s_{i+1}| ≤ max(m_i , m_{i+1})$。$n ≤ 10^5$。

首先，我们发现 $k=2$ 时一定有解——当 $|s_1-s_2|$ 最小时，一定满足 $|s_1-s_2|<\max{a_i}$ 的性质。

我们先将这个序列任意地分成 $k$ 部分，然后每次随便找一对不满足条件的相邻的两端，把它们中间的分界线调整为合法的一个分界线。不断这样操作下去，一定可以使局面在有限步内收敛至合法局面。因为，$\sum s_i^2$ 是在不断缩小的；当 $\sum s_i^2$ 缩小至最小时，一定是合法的，不然就可以继续缩小。

依据这个性质，我们实际上就是要求出一种使 $\sum s_i^2$ 最小的划分。直接 wqs 二分即可。

Example 10. Clique

(2020 Petrozavodsk Winter Camp Jagiellonian U Contest Problem D)

给一个圆的 $n$ 条圆弧，选出一个尽量大的子集使得其中的圆弧两两有交。$n ≤ 3000$。

枚举选出的圆弧中最短的一根。显然不会有其它线段被其包含，且包含它的线段一定合法。唯独需要考虑的，是与它相交且不包含的线段——分成包含其左端点还是包含其右端点讨论，而每条这样的线段都可以用两维坐标（分别对应其两个端点的位置）表示，于是就变为了一个平面问题，线段树加速动态规划即可。

Example 11. LIS vs. LDS

(Source: Yandex Algorithm 2018 Final Round Problem D)

给一个排列, 求一组不相交的 LIS 和 LDS。$n ≤ 5 × 10^5$。

显然一个 LIS 与 LDS 最多只能在一处相交。设 $A_i$ 表示经过 $i$ 的 LDS 数量，那么一个 LIS 不合法，当且仅当 $\sum A_{lis_i}=$ 总数。我们直接在求 LIS 的过程中维护 $A$ 的和，只需维护两种不同的就行。在对质数取模的意义下计算即可。

Example 12. [CF868F] Yet Another Minimization Problem

将一个长度为 $n$ 的序列分为 $k$ 段，一段 $[l,r]$ 的代价是 $l ≤ i < j ≤ r$，$a_i = a_j$ 的 $(i, j)$ 对数。最小化分割代价。$n ≤ 10^5 , k ≤ 20$。

对于 $f_{i}=\min\{g_j+calc(j,i)\}$ 型的 dp，不难想到决策单调性。而分治型实现的决策单调性在计算 $calc$ 时使用莫队的复杂度是不变的。