AtCoder DP 专题做题记录

· · 个人记录

前言

没写记录的题目就是没 A，原因可能是太简单了或太难了。

upd on 25.10.2 更新了 W 的线段树优化 DP 以及 Z 的斜率优化 DP。

C

link. & code.

转移显然。初始值 $dp_{1,0/1/2}=a_{1,0/1/2}$。答案 $\max(dp_{n,0/1/2})$。 另：**连续两天以上**其实是**连续两天及以上**，刚开始以为是**连续两天以上**然后式子推复杂了，然后 WA on 样例#3。 ## E [link.](https://www.luogu.com.cn/problem/AT_dp_e) & [code.](https://atcoder.jp/contests/dp/submissions/59073108) 一个很有趣的题目。 发现是 0-1 背包板子，但是 $w$ 过大导致普通做法不可做。 发现数据的弱点在于 $v$ 很小，考虑将 $v$ 作为下标转移。$dp_{i,j}$ 表示当前选到第 $i$ 个，总价值为 $j$ 的最小重量。那么易得转移 $dp_{i,j}=\min(dp_{i-1,j-v_i+w_i})$，同时也可以不选，即 $dp_{i,j}=dp_{i-1,j}$。 数据小到甚至不用滚动数组优化，好耶。 ## G [link.](https://www.luogu.com.cn/problem/AT_dp_g) & [code.](https://atcoder.jp/contests/dp/submissions/59073288) 一眼 SPFA，二眼**有向无环图**，带着疑惑往后看发现逆天数据范围 $n\leq 10^5$，好，SPFA 不超时才怪。 于是考虑**有向无环图**这个条件，想到记搜，$dp_{i}$ 表示从 $i$ 开始走走出来的最长路，那么答案为 $\max(dp_i)$。然后枚举起点，记忆化走就行了。对于边 $u\rightarrow v$，有 $dp_u=dp_v+1$。 时间显然优秀。 ## I [link.](https://www.luogu.com.cn/problem/AT_dp_i) & [code.](https://atcoder.jp/contests/dp/submissions/59073432) 其实没有什么辨识度。 $dp_{i,j}$ 表示选到第 $i$ 个硬币，投了 $j$ 次正面的概率。显然有转移 $dp_{i,j}=dp_{i-1,j-1}\times p_i+dp_{i-1,j}\times(1-p_i)$。答案是 $\sum_{i=\frac{n+1}{2}}^{n} dp_{n,i}$。 ## J [link.](https://www.luogu.com.cn/problem/AT_dp_j) & [code.](https://atcoder.jp/contests/dp/submissions/59074782) 期望 DP。 做这种题目的时候总是苦恼：因为总是会有状态会选无限次但是收敛，这个时候就不好正着转移。这道题亦如此。看了一下题解，知道了：正着转移不行就反着转移。 发现这道题的弱点在于：$a_i$ 只有 $1,2,3$ 三种取值，那么考虑设计 DP 状态：$dp_{i,j,k}$ 表示当前分别剩下 $i,j,k$ 个装有 $1,2,3$ 个寿司的盘子。 那么有转移： - 随机到寿司数为 $0$ 的盘子：$dp_{i,j,k}=(dp_{i,j,k}+1)\times \frac{n-i-j-k}{i+j+k}$。 - 随机到寿司数为 $1$ 的盘子：$dp_{i,j,k}=(dp_{i-1,j,k}+1)\times \frac{i}{i+j+k}$。 - 随机到寿司数为 $2$ 的盘子：$dp_{i,j,k}=(dp_{i+1,j-1,k}+1)\times \frac{j}{i+j+k}$。 - 随机到寿司数为 $3$ 的盘子：$dp_{i,j,k}=(dp_{i,j+1,k-1}+1)\times \frac{k}{i+j+k}$。 那么答案为：$dp_{i,j,k}=\frac{(n-i-j-k)\times dp_{i,j,k}+i\times dp_{i-1,j,k}+j\times dp_{i+1,j-1,k}+k\times dp_{i,j+1,k-1}+n}{n}$。 发现 $(n-i-j-k)\times dp_{i,j,k}$ 这个东西正是我们苦恼的点所在：自己从自己转移。 没关系，我会移项！ 将 $\frac{(n-i-j-k)\times dp_{i,j,k}}{n}$ 移到左边，即 $dp_{i,j,k}\times \frac{i+j+k}{n}=\frac{i\times dp_{i-1,j,k}+j\times dp_{i+1,j-1,k}+k\times dp_{i,j+1,k-1}+n}{n}$，将 $\frac{i+j+k}{n}$ 除过去，即 $dp_{i,j,k}=\frac{i\times dp_{i-1,j,k}+j\times dp_{i+1,j-1,k}+k\times dp_{i,j+1,k-1}+n}{i+j+k}$，那么就大功告成了。 那么答案是 $dp_{c_1,c_2,c_3}$，$c_i$ 表示初始时盘子中装了 $i$ 个寿司的盘子数量。 ## K [link.](https://www.luogu.com.cn/problem/AT_dp_k) & [code.](https://atcoder.jp/contests/dp/submissions/59075077) 带有博弈论元素的 DP。 同样的，做这种题目的时候总是纠结于“最优策略”。 其实只要找准结束状态，然后去 DP 这个状态是否可以达到结束状态就行了。 发现当拿完的时候当前操作者必败。有发现若操作奇数次拿完则先手胜，否则后手。 于是设状态 $dp_i$ 表示是否可以拿奇数次拿了了 $i$ 个石子，转移显然：若存在 $j\in[1,n]$ 使得 $dp_{i-a_j}=0$，那么 $dp_{i}=1$。即从必败状态 $dp_{i-a_j}$ 能转移到必胜状态 $dp_i$。 不用初始化，直接全部赋权为 $0$，因为没有操作的时候所有状态都是必败。 ## L [link.](https://www.luogu.com.cn/problem/AT_dp_l) & [code.](https://atcoder.jp/contests/dp/submissions/59075315) 考虑区间 DP。 刚开始为什么会想 $dp_{l,r,0/1}$ 表示 $l,r$ 区间，当前从左/右边转移…… 其实第三维 $0/1$ 是冗余状态。 直接 $dp_{l,r}$ 表示操作剩下区间 $[l,r]$，最后答案。 若当前区间是第一个人操作，那么 $dp_{l,r}=\max(dp_{l+1,r}+a_l,dp_{l,r-1}+a_r)$，表示第一个人想要这个值大。 否则 $dp_{l,r}=\min(dp_{l+1,r}-a_l,dp_{l,r-1}-a_r)$，表示第二个人想要这个值小。 然后答案是 $dp_{1,n}$。 ## M [link.](https://www.luogu.com.cn/problem/AT_dp_m) & [code.](https://atcoder.jp/contests/dp/submissions/59079485) 或许是训练前缀和优化 DP。 $dp_{i,j}$ 表示选到第 $i$ 个选了总和 $j$ 的方案数。 那么有 $dp_{i,j}=\sum_{k=\max(0,j-a_i)}^j dp_{i-1,k}$。 时间复杂度 $\mathcal{O(nm^2)}$，发现会超时。 发现可以前缀和优化 $\sum_{k=\max(0,j-a_i)}^j dp_{i-1,k}$，于是 $\mathcal{O(nm^2)}\rightarrow \mathcal{O(nm)}$，可过。 ## N [link.](https://www.luogu.com.cn/problem/AT_dp_n) & [code.](https://atcoder.jp/contests/dp/submissions/59075461) 石子合并弱化版，典中典，不讲了。 ## P [link.](https://www.luogu.com.cn/problem/AT_dp_p) & [code.](https://atcoder.jp/contests/dp/submissions/59075589) 树形 DP 板。算是复习了一下树形 DP？ $dp_{i,0/1}$ 表示以 $i$ 为根节点的子树，第 $i$ 个点染黑/白色的方案数。 那么对于边 $u\rightarrow v$，$dp_{u,0}=\prod dp_{v,1},dp_{u,1}=\prod (dp_{v,0}+dp_{v,1})$。 答案是 $dp_{1,0}+dp_{1,1}$。 ## Q [link.](https://www.luogu.com.cn/problem/AT_dp_q) & [code.](https://atcoder.jp/contests/dp/submissions/59079869) 感觉自从了解到做类最长上升子序列还可以用树状数组做以后就彻底摒弃了二分做法。~~反正复杂度都一样而且树状数组更好理解不是？~~ 这道题仍然是类最长上升子序列，设 $dp_i$ 表示以第 $i$ 个数结尾，选中的最长上升子序列的最大权值。 那么用树状数组维护，不太好讲转移，放个代码： ```cpp for(int i=1;i<=n;i++){ dp[i]=qy(a[i]-1)+w[i];// 表示从 a[j]<a[i] 的 j 中选出权值最大的那一个 qy(a[i]-1), 然后加上选 a[i] 的贡献 w[i] upd(a[i],dp[i]);// 插入 } ``` 注意树状数组的 $tree$ 可能要用 `map` 维护因为 $a_i\leq 10^9$。 ## R [link.](https://www.luogu.com.cn/problem/AT_dp_r) & [code.](https://atcoder.jp/contests/dp/submissions/59080792) 第一眼：这不是随便转移吗？若 $a_{i,j}$ 为 $1$ 表示 $i$ 可以从 $j$ 转移。 第二眼：啊？$K\leq 10^{18}$。 第三眼：哦！矩阵快速幂优化 DP！ 题目甚至十分贴心的把转移矩阵都输给你了，赞美良心出题人。 设输入矩阵为 $C$，那么最后矩阵为 $C^K$，答案是 $C^K$ 中的元素之和。 这个转移还是不难想到的吧。 ## S [link.](https://www.luogu.com.cn/problem/AT_dp_s) & [code.](https://atcoder.jp/contests/dp/submissions/59081762) [我的数位 DP 学习笔记。](https://www.luogu.com.cn/article/gfqdr9ov) 一眼数位 DP 板子。算是复习了数位 DP 的记搜方式？ 随便记搜，$dp_{pos,num}$ 表示当前在第 $pos$ 位，数字和对 $D$ 的取模结果为 $num$ 的方案数，然后直接记搜转移就行了。 另：如果不判前导 0 标记的话最后答案要 -1，因为 0 是不能被算在内的。 ## T [link.](https://www.luogu.com.cn/problem/AT_dp_t) & [code.](https://atcoder.jp/contests/dp/submissions/59082207) 联赛考过加强版（有一个建模转化），好活。 似乎又是考察优化 DP？ $dp_{i,j}$ 表示 $1\sim i$ 个数，第 $i$ 个数排名 $j$ 的方案数。 那么易得转移： - 若 $s_i=$ `<`，那么 $dp_{i,j}=\sum_{k=j}^{i-1} dp_{i-1,k}$。 - 否则 $dp_{i,j}=\sum_{k=1}^{j-1} dp_{i-1,k}$。 前缀和优化即可将复杂度从立方级别转化为平方级别。 ## U [link.](https://www.luogu.com.cn/problem/AT_dp_u) & [code.](https://atcoder.jp/contests/dp/submissions/59083253) 看到数据范围 $n\leq 16$，想到状压 DP。 $dp_i$ 表示当前选数的状态为 $i$，0/1 分别表示这个数选/没选。 那么设 $j$ 是 $i$ 的某个子集状态，那么可以有 $dp_i=dp_{i\oplus j}+S_j$，表示在当前轮选择了子集 $j$，将 $j$ 中的所有数分成一组。而将 $j$ 中的所有数分成一组的贡献是 $S_j$。 现在考虑如何求解 $S_j$，若 $j$ 中存在 $2$ 个无序对 $(x,y)$ 满足 $j$ 的第 $x,y$ 位均为 1，那么 $S_j\leftarrow S_j+a_{x,y}$。 另：枚举子集有一个高效的方式 `for(int j=i;j;j=(j-1)&i)`，表示枚举 $i$ 的子集 $j$。 ## W [link.](https://www.luogu.com.cn/problem/AT_dp_w) & [code.](https://atcoder.jp/contests/dp/submissions/68481762) 考虑朴素的转移：$dp_i$ 表示当前到 $i$ 且强制选择 $i$ 的最大贡献。大概就是 $dp_i\leftarrow dp_j+w(j+1,i)$。考虑以区间的贡献去统一更新点的贡献，而不是对于每个点单独附加区间的贡献。 具体来说，我们将区间按顺序扫描线，对于区间 $[l,r]$，贡献为 $w$。然后按顺序扫下标。我们在加入 $l$ 时将 $dp_{0\sim l-1}$ 全部 $+w$，表示从 $dp_{0\sim l-1}$ 转移至 $dp_l$ 时都会新增区间 $[l,r]$，所以加上 $w$ 的贡献。 同时，当扫完一个区间，到了 $r+1$ 时，从 $[0,l-1]$ 转来的就不能加上 $w$ 的贡献了，因为 $[0,l-1]$ 和 $r+1$ 都不包含 $w$，那么将 $dp_{0\sim l-1}$ 集体 $-w$。转移时，有 $dp_i=\max_{j=0}^{i-1}dp_j$。 考虑将 $dp_i$ 当作线段树上点 $i$ 的权值，那么就是一个很简单的区间修改和区间查询。 ## Y [link.](https://www.luogu.com.cn/problem/AT_dp_y) & [code.](https://atcoder.jp/contests/dp/submissions/59086895) [我的计数 DP 学习笔记。](https://www.luogu.com.cn/article/kdihsjom) 计数 DP 模板题，蓝书 0x5C 节例题 1。之前一直想在洛谷上找原没找着来着。 技巧类似，找准**基准点**。 首先发现 $H,W$ 都很大但 $n$ 很小，考虑将复杂度往 $n$ 上靠。 那么我们设第一个走到的点为基准点。可以设 $dp_i$ 表示从左上角走到排序后的第 $i$ 个格子的方案数，且途中不经过任何其他的黑点。设终点 $(H,W)$ 为第 $n+1$ 个格子。答案即为 $dp_{n+1}$。 我们又知道：从一个长、宽分别为 $H,W$ 的矩阵的左上角走到右下角的方案数为 $C_{H-1+W-1}^{H-1}$，所以我们可以得到方程：$dp_{i}=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=1}^{i-1} dp_j\times C_{x_i+y_i-x_j-y_j}^{x_i-x_j}$，表示从左上角走到 $i$ 的方案数减去从左上角走到 $i$ 前面任何一个数的方案数，就是最后的答案。 ## Z [link.](https://www.luogu.com.cn/problem/AT_dp_z) & [code.](https://atcoder.jp/contests/dp/submissions/69776777) [我的斜率优化 DP 学习笔记。](https://www.luogu.com.cn/article/yajbdhqp) 直接拆式子：$dp_i=\min\{dp_j+(h_i-h_j)^2+C\}$。 那么 $dp_i=dp_j+{h_i}^2-2h_ih_j+{h_j}^2+C$。 那么 $dp_j+{h_j}^2=2h_ih_j+(dp_i+C)$。那么： $\begin{cases} y_j=dp_j+{h_j}^2 \\ k_i=2h_i \\ x_j=h_j\\ b_i=dp_i+C\\ \end{cases}

套路化地去做就行了。

总结

是一个不错的板刷各种 DP 的综合专题。