At_dp 选讲

前言

这一次做 Atcoder 上的 dp 题目，将26道题都刷了一遍，各个方面都有涉及，但每个都只涉及一到两题，总体来说掌握的不是很扎实，但现将这些东西写成blog巩固一下。

背包问题

背包问题分为很多种，常见的有01背包、多重背包、完全背包、分组背包等等，问题都是关于给定 $n$ 个限制 $w_i$ 和价值 $v_i$，求在 $\sum w_i\le W$ 的情况下最大化 $\sum v_i$。在这里，Atcoder 上只给出了01背包和它的状态设计优化。

01背包 (Atcoder_dp_d Knapsack1)

对于 $n$ 个物品，每个物品只能取1次，问 $\sum w_i\le W$ 的情况下最大化的 $\sum v_i$。

考虑我们要用到什么状态，首先需要选到了第几个物品，然后需要知道现在的重量是多少，以免超过 $W$。那么不妨设 $f_{i,j}$ 表示选到第 $i$ 个物品还剩 $j$ 的容量的最大价值，于是显然：

$$f_{i,j}=\max{f_{i-1,j},f_{i-1,j-w_i}+v_i}$$

同时注意到 $i$ 只与 $i-1$ 有关，因此可以压掉第一维，变成

$$f_j=\max{f_j,f_{j-w_i}+v_i}$$

注意到此时后面的值需要用到前面的，因此如果先更新前面的会使后面的决策出现错误，因此循环需要从后往前。

01背包：状态设计优化 (Atcoder_dp_e Knapsack2)

注意到此时的 $W$ 来到 $10^6$，而相应的 $v_i$ 是 $10^3$，如果再设 $w$ 为状态就会 $\text{TLE}$，于是很自然的想到可以使用 $v_i$ 来代替 $w_i$，反而将 $w_i$ 存储在数组中。

因此可以设出状态 $f_i$ 表示价值为 $i$ 的最小重量是多少。这里已经将第一维压掉。那么显然对于 $f_i$，能够写出转移方程

$$f_i=\min{f_i,f_{i-v_i}+w_i}$$

其中 $f_i$ 注意最初设置为 $\mathrm{INF}$，求答案的时候从后往前遍历 $f_i$ 找到第一个 $f_i\le W$ 的即可。

拓扑上 DP (Atcoder_dp_g Longest Path)

拓扑上的 $DP$ 有一个显著的特点，也就是图是DAG，这样图上没有环就可以很好地满足动态规划的无后效性。具体地，对于一个点 $u$，可以从所有 $u\in son_v$ 的 $v$ 上转移过来。当 $u$ 的入度变为0，就可以把它入队然后更新它的 $son_u$ 了。如果给的题不是 $\mathrm{DAG}$，如果题目条件允许可以进行 $\mathrm{Tarjan}$ 缩点，然后变成 $\mathrm{DAG}$，之后就可以动态规划了。

对于这个问题，设 $f_i$ 是终点为 $i$ 的最长路径。那么最开始将 $in_i=0$ 的点，不难得到方程

$$f_u=\max\limits_{v \in son_u}{f_u}+1$$

在拓扑排序的时候进行 $\mathrm{DP}$ 即可。

期望 DP (Atcoder_dp_j Sushi)

对于期望 DP，它是一类求概率的动态规划。一般需要倒推概率。（就目前我也不大知道它的具体定义和套路是什么。。。）

朴素的想法是设 $f_{a_1,a_2,\dots,a_n}$，代表第 $i$ 位还剩下 $a_i$ 个寿司的概率。于是能得到

$$f_{a_1,a_2,\dots,a_n}=1+\frac{1}{n}\sum\limits_{i=1}^n f_{a_1,a_2,\dots,\max{a_i-1,0},\dots,a_n}$$

显然，这是过不了的。我们分析一下状态设计，注意到我们并不关心每个盘子还有几个寿司，我们只需要知道剩下 $i$ 个寿司都有多少盘即可。于是设 $f_{a,b,c,d}$ 表示剩下 $0/1/2/3$ 个寿司的盘子分别有 $a/b/c/d$ 个，于是不难得到

$$f_{a,b,c,d}=1+\frac{a}{n}f_{a,b,c,d}+\frac{b}{n}f_{a+1,b-1,c,d}+\frac{c}{n}f_{a,b+1,c-1,d}+\frac{d}{n}f_{a,b,c+1,d}$$

移项得到：

$$\frac{b+c+d}{n}f_{a,b,c,d}=1+\frac{b}{n}f_{a+1,b-1,c,d}+\frac{c}{n}f_{a,b+1,c-1,d}+\frac{d}{n}f_{a,b,c+1,d}$$

然后系数化一：

$$f_{a,b,c,d}=\frac{n}{b+c+d}+\frac{b}{b+c+d}f_{a+1,b-1,c,d}+\frac{c}{b+c+d}f_{a,b+1,c-1,d}+\frac{d}{b+c+d}f_{a,b,c+1,d-1}$$

但是 $O(n^4)$ 的复杂度还是没法通过本题。但是注意到 $a+b+c+d=n$ 是恒定不变的因此可以压掉一位 $a$，正好 $a$ 与转移的系数无关，压掉之后就变成：

$$f_{b,c,d}=\frac{n}{b+c+d}+\frac{b}{b+c+d}f_{b-1,c,d}+\frac{c}{b+c+d}f_{b+1,c-1,d}+\frac{d}{b+c+d}f_{b,c+1,d-1}$$

然后你就发现 Accept!。

前缀和优化DP (Atcoder_dp_m Candies)

对于形如

$$f_{i,j}=val(i)+\sum\limits_{k=1}^j f_{i-1,k}$$

的式子，我们可以进行前缀和优化，即在转移时记录一个 $s_{i,j}=\sum\limits_{k=1}^j f_{i,k}$，于是转移就变成

$$f_{i,j}=val(i)+s_{i-1,j}$$

实现 $O(1)$ 转移。

例如本题，我们设 $f_{i,j}$ 表示前 $i$ 个小盆友分 $j$ 个苹果有多少种分配方式，枚举这一个小盆友的苹果数量，不难得到：

$$f_{i,j}=\sum\limits_{k=0}^{\min{a_i,j}}f_{i-1,j-k}-\sum\limits_{k=0}^{\max{j-a_i-1,0}}f_{i,k}$$

因此记录一个 $s_{i,j}=\sum\limits_{k=0}^j f_{i,j}$，就可以 $O(1)$ 转移了。

区间DP (Atcoder_dp_n Slimes)

如果一个问题可以通过合并两个小的区间来得到最终的答案，（在数据范围不大的情况下）就可以使用区间 DP 解决这个问题。一般地，我们设 $f_{i,j}$ 表示已经处理完区间 $[i,j]$ 的问题的最大/小代价。关于转移，对于 $f_{i,j}$，我们枚举中间断点 $k$，不难得到方程

$$f_{i,j}=\max\limits_{k=i}^{j-1} f_{i,k}+f_{k+1,j}+val(i,j,k)$$

关于本题，我们设 $f_{i,j}$ 表示合并区间 $[i,j]$ 的最小代价，然后枚举 $k$，显然 $val(i,j,k)=\sum\limits_{l=i}^j a_l$，即与 $k$ 无关，预处理前缀和即可。

状压DP (Atcoder_dp_o Matching)

对于数据范围在 $20$ 之内的动态规划，我们可以考虑进行状态压缩。状态压缩即在数据范围不到的情况下将选/不选或其它状态进行二进制压缩，以方便枚举子集来求答案。