AtCoder DP系列刷题记录
Yizhixiaoyun
·
·
个人记录
https://www.luogu.com.cn/training/313353
直面自己的弱点。
标 * 的为在做题过程中有看题解的题。
A Frog 1
$$dp_i+=\min(|a_i-a_{i-1}|,|a_i-a_{i-2}|)$$
## B Frog 2
很快就写完了，但是一直调了十分钟，耻辱啊。
$dp_i$ 表示跳到第 $i$ 块石头的最小花费。显然如果反着跳，第 $i$ 根木桩只能从第 $i+1$ 或 $i+2$ 木桩上跳到，则有：
$$dp_i=\min(dp_{i+1}+|a_i-a_{i+1}|,dp_{i+2}+|a_i-a_{i+2}|)$$
## C Vacation
~~语文课花两分钟想出来的。~~
$dp_{i,j}$ 表示到第 $i$ 天时，做第 $j$ 件时获得的最大总幸福度。显然对于 $a_i$，它只能接受 $b_{i-1}$ 和 $c_{i-1}$ 的转移，其他两边情况相同，则有：
$$dp_{i,0}=\max(dp_{i-1,1},dp_{i-1,2})+a_i$$
$$dp_{i,1}=\max(dp_{i-1,0},dp_{i-1,2})+b_i$$
$$dp_{i,2}=\max(dp_{i-1,0},dp_{i-1,1})+c_i$$
## D Knapsack 1
$01$ 背包板子，不讲了。
## E Knapsack 2
与 $01$ 背包基本一致，但数据范围大了很多，将 $\text{dp}$ 数组表示的东西换一下就行了，不表示价值，表示重量。像 $01$ 背包一样压维，则有：
$$dp_j=\min(dp_j,dp_{j-v_i}+w_i)$$
## F LCS
经典题，就是恶心了一点。
$dp_{i,j}$ 表示到 $s$ 的第 $i$ 位，$t$ 的第 $j$ 位时的最大公共子序列长度，则有：
$$dp_{i,j} = \begin{cases}
dp_{i-1,j-1}+1 ,& a_i=b_j\\
\max(dp_{i-1,j},dp_{i,j-1}) ,& \text{otherwise.}
\end{cases}$$
然后再记录一个 $\text{from}$ 数组，方便找到这一位是从前一位中的 $dp_{i-1,j-1},dp_{i-1,j},dp_{i,j-1}$ 的哪个转过来的。
然后从后往前再跑一遍找到这个最大公共子序列即可。
## G Longest Path
拓扑排序模板题。
$dp_i$ 表示以 $i$ 为终点的路径最大长度。若有 $v$ 到 $u$，则有：
$$dp_u=\max(dp_u,dp_v+1)$$
然后先跑出拓扑序，然后按序 $\text{dp}$ 即可。
## H Grid 1
突然冒出来一道比前面所有题都简单的题...
$dp_{i,j}$ 表示到第 $i$ 行第 $j$ 列有多少种走法。则有：
$$dp_{i,j} = \begin{cases}
dp_{i,j-1}+dp_{i-1,j} ,& a_{i,j}=\space . \space\\
0 ,& \text{otherwise.}
\end{cases}$$
## I Coins
$dp_{i,j}$ 表示前 $i$ 个硬币中，有 $j$ 个正面朝上的概率，则有：
$$dp_{i,j}=dp_{i-1,j-1} \times p_i+dp_{i-1,j} \times (1-p_i)$$
## *J Sushi
其实不难，当时脑子没转过来。
$dp_{i,j,k,l}$ 表示有 $i$ 个没有寿司的盘子、$j$ 个有 $1$ 个寿司的盘子、$k$ 个有 $2$ 个寿司的盘子时的期望次数，$l$ 个有 $3$ 个寿司的盘子时的期望次数，则有：
$$dp_{i,j,k,l}=\dfrac{a}{n} \times dp_{i,j,k,l}+\dfrac{b}{n} \times dp_{i+1,j-1,k,l}+\dfrac{c}{n} \times dp_{i,j+1,k-1,l}+\dfrac{d}{n} \times dp_{i,j,k+1,l-1}+1$$
移项得：
$$dp_{i,j,k,l}=\dfrac{j}{j+k+l} \times dp_{i+1,j-1,k,l}+\dfrac{k}{j+k+l} \times dp_{i,j+1,k-1,l}+\dfrac{l}{j+k+l} \times dp_{i,j,k+1,l-1}+\dfrac{n}{j+k+l}$$
发现有 $0$ 个寿司的盘子数是可以通过其他三个盘子的数量和总数 $n$ 算出来的，压掉一维，然后有：
$$i=n-j-k-l$$
转移方程：
$$dp_{j,k,l}={\dfrac{j}{j+k+l} \times dp_{j-1,k,l}+\dfrac{k}{j+k+l} \times dp_{j+1,k-1,l}+\dfrac{l}{j+k+l} \times dp_{j,k+1,l-1}+\dfrac{n}{j+k+l}}$$
## K Stones
当一名玩家操作时剩余石子为 $0$，则另一位玩家必胜，由此可以倒推。
$dp_i$ 表示在剩余 $i$ 个石子时，先手胜还是后手胜，则有：
$$dp_i = \begin{cases}
1 ,& a_j \le i,dp_{i-a_j}=0\\
0 ,& \text{otherwise.}
\end{cases}$$
## L Deque
区间 $\text{dp}$ 典题。
$dp_{l,r}$ 表示在剩余下标为 $[l,r]$ 的区间时，当前取数的人能获得的最大数字和，则有：
$$dp_{l,r}=\max(-dp_{l+1,r}+sum_r-sum_{l-1},-dp_{l,r-1}+sum_r-sum_{l-1})$$
直接搞会超时，所以用前缀和维护即可。
## M Candies
$\text{dp}$ 五分钟，优化半小时。
$dp_{i,j}$ 表示前 $i$ 个人分 $j$ 颗糖的方案数，则有：
$$dp_{i,j}=\sum_{l=0}^{a_i}{dp_{i-1,j-l}}$$
然后我就自信的交了一发，由于前面十分顺利，我甚至没发现复杂度是错的...
之后加了个前缀和，但是调了好久，最后才发现 $j-a_{i-1}$ 有可能小于 $0$，警示后人。
## N Slimes
区间 $\text{dp}$ 模板题。
$dp_{i,j}$ 表示 $a_i$ 合并到 $a_j$ 的最小代价，枚举中间点 $k$，则有：
$$dp_{i,j}=\min(dp_{i,j},dp_{i,k}+dp_{k,j}+\sum_{l=i}^{j}{a_l})$$
前缀和维护即可。
## *O Matching
第一道蓝题出现了！
应该是状压 $\text{dp}$ 模板题。~~经典写不出状压。~~
定义集合 $S$，当中只包含女人的编号，然后去枚举第 $i$ 个男人和哪个女人匹配。
$dp_S$ 表示前 $i$ 个男人与 $S$ 中的女人的匹配方案数，则有：
$$dp_S=\sum_{}^{}{dp_{S-i}},i \in S$$
然后将它变为一个 $n$ 位的二进制数，如果右往左第 $i$ 位为 $1$，就表示 $S$ 有编号为 $i$ 的女人，否则没有。
然后状压 $\text{dp}$ 即可。
## P Independent Set
简单树形 $\text{dp}$。
$dp_{i,j}$ 表示将 $i$ 节点染成 $j$ 号颜色的方案数。不能连续染 $2$ 个黑，所以黑的状态只能由白来传递，而白可以由黑白传递，则有：
$$dp_{u,0} \times =dp_{v,1}$$
$$dp_{u,1} \times =dp_{v,0}+dp_{v,1}$$
## Q Flowers
$dp_i$ 表示在满足条件下前 $i$ 朵花能达到的权值最大值，则有：
$$dp_i=a_i+\max_{j=1}^{i-1}dp_j$$
然后树状数组维护 $\max(dp_1,dp_{i-1})$ 即可。
## *R Walk
$dp_{u,v,len}$ 表示 $u$ 到 $v$，长度为 $len$ 的条数。枚举中点 $mid$，则有：
$$dp_{u,v,s}=dp_{u,mid,len-1} \times dp_{mid,v,1}$$
然后使用矩阵快速幂维护即可。
## *S Digit Sum
第一次做数位 $\text{dp}$。
特别感谢 [$\text{yinhee}$](https://www.luogu.com.cn/user/578590) 大佬，他的讲解令我受益匪浅。
$dp_{pos,res,lim}$ 表示当前枚举到从高位往低位数第 $pos$ 位，数字和取模后的余数为 $res$ 时的方案数，其中 $lim$ 可以理解为一个布尔值，$0$ 表示没有到上限，$1$ 表示到了上限。
然后是一个数位 $\text{dp}$ 的板子，我特别讲一下这一行代码：
```cpp
tot+=dfs(pos-1,(res+i)%d,(lim!=0)&&(i==maxx));
```
其中 $maxx$ 是当前枚举位可选的最大值。
这里就是在枚举第 $pos-1$ 位，选择了 $i$ 作为这位的数，$res+i$ 就是新的数字和。而后面的判断条件就是在看枚举到目前为止，该数是否还与 $k$ 的前缀相同，是就说明到目前为止还是最大的，否则就不是。
## T Permutation
不会，先鸽着。
## U Grouping
范围识状压。
$dp_i$ 表示状态为 $i$ 时的最大收益。那么我们可以枚举其子集 $j$，$k$ 为其补集，则有：
$$dp_i=\max(dp_i,dp_j+dp_k)$$
## V Subtree
$dp_u$ 表示 $u$ 号节点染黑后，其子树内黑点构成连通块的方案数，则有：
$$dp_u \prod_{v \in son_u}dp_v+1$$
然后换根，则有：
$$ans_{dp_u}=\frac{ans_{dp_u}}{dp_u+1}$$
然后有：
$$ans_u \times =ans_{dp_u}+1$$
## W Intervals
## X Tower
好水的题，秒了。
看到题面就知道是背包，唯一的问题是怎么优化其复杂度。
如果将 $x$ 放于 $y$ 上，那么上面还能堆 $x_s-y_w$ 的东西，反之则能堆 $y_s-x_w$ 的东西，所以若有 $x_s-y_w<y_s-x_w$，则将第 $x$ 个箱子放在第 $y$ 个箱子下更优。
排序完再跑背包即可。
## Y Grid 2
## Z Frog 3