DP练习题 解题报告

· · 个人记录

嗯...看看我能坚持几天。估计到不了三天

2024.09.05

[ABC369F] Gather Coins

倒序枚举每一枚硬币，在右下方找 dp 值最大的硬币进行转移就行了。寻找的过程使用线段树优化，时间复杂度 O(n\log n)。

[AT_dp_m] Candies

设 dp_{i,j} 为前 i 个人分 j 个糖的方案数。转移为 dp_{i,j} \gets \sum_{k=j-a_i}^j dp_{i-1,k}，使用前缀和优化转移，时间复杂度 O(nk)。

[AT_dp_o] Matching

状压 DP。朴素想法是设 dp_{i,s} 为左部前 i 个元素和右部集合 s 匹配的方案数，转移时枚举第 i 个人的匹配，但是时间复杂度 O(n^2 2^n) 无法接受。

发现在合法方案下 i 和 s 的大小始终相等，因此压掉第一维即可。时间复杂度 O(n 2^n)。

[AT_dp_u] Grouping

也是状压 DP。设 dp_s 为选取集合 s 获得的最大分值，有转移 dp_s \gets \max_{v \in s} dp_{s \oplus v} + w_v，其中 w_v 表示集合 v 的分值。

### 2024.09.06 [P1373 小 a 和 uim 之大逃离](https://www.luogu.com.cn/problem/P1373) 状态比较一眼，$dp_{i,j,k}$ 表示在位置 $(i,j)$，差值为 $k$ 的方案数。由于起始位置任意，因此还要再加一维 $0,1$ 表示现在是谁取。时间复杂度 $O(nmk)$。 转移从上边和左边的格子取，记得把差值取模。 ### 2024.09.07 [[ABC370E] Avoid K Partition](https://www.luogu.com.cn/problem/AT_abc370_e) 设 $dp_i$ 为以第 $i$ 位结尾，且不出现和为 $k$ 的子段的方案数。发现一个方案能从前面的某个方案转移当且仅当这段区间和不为 $k$。因此对序列做前缀和，用 `map` 优化即可做到 $O(n \log n)$。 ### 2024.09.08 [[ABC366F] Maximum Composition](https://www.luogu.com.cn/problem/AT_abc366_f) 首先采用交换法求出嵌套顺序更优的条件，按此条件排序。 然后 DP，$dp_{i,j}$ 表示前 $i$ 个函数选了 $j$ 个的最大值。 转移考虑前缀最大值，维护一下即可做到 $O(n \log n+nk)$。 ### 2024.09.09 [P1272 重建道路](https://www.luogu.com.cn/problem/P1272) 树形DP。设 $dp_{i,j}$ 为以 $i$ 为根的子树中剖出 $j$ 个节点的最小操作数。转移实际上就是树形背包。 注意统计答案小坑：剖出来的子树不一定以 $1$ 为根，如果不以 $1$ 为根，操作次数要加一用来跟父亲断开。 ### 2024.09.12 [CF115E Linear Kingdom Races](https://www.luogu.com.cn/problem/CF115E) 对于这种区间贡献，我们采取在右端点计算贡献的方法，即可做到不重不漏。 设 $dp_i$ 为考虑前 $i$ 条道路的最大利润。 首先不选时有 $dp_i=dp_{i-1}$，然后考虑选 $i$，有转移 $dp_i=\max\{ dp_j - cost(j+1,i) + val(j+1,i)\}$。 这个转移表示我们修建 $[j+1,i]$ 这一段的道路，消耗这一段道路总金额并且赚取在这个区间内举行的比赛收益。 朴素转移是 $O(n^2)$ 的，不能通过。我们考虑每个右端点新加区间对决策的影响。 假如我们增加了一个区间 $[L,R]$，那么我们在新修建的路的左端点大于等于 $L$ 时都能吃到利润，也即 $dp_0$ 到 $dp_{L-1}$ 的决策新增了价值。 发现这是一个区间加操作，我们要快速实现区间加和区间查询最大值，使用线段树即可。 那么让线段树的 $[j,j]$ 区间维护 $dp_j-cost(j+1,i)+val(j+1,i)$，对于每一轮循环，我们要做的事情有： + 对新增加的区间做区间加 + 对前面所有点做区间减，减掉修建 $i$ 的成本 + 查询 $dp_i$ 并放入线段树 那么就做完了。时间复杂度 $O(n \log n)$。 ### 2024.09.13 [P7098 [yLOI2020] 凉凉](https://www.luogu.com.cn/problem/P7098) 状压 DP。设 $dp_{i,s}$ 表示修建了深度不大于 $i$ 的铁路，且通行的列车状态为 $s$ 的最小代价。 我们先预处理出来每个子集是否能在同一高度，如果能，再求出在每个高度需要的花费。 转移有 $dp_{i,s}=\min \{ dp_{i-1,u} +val_{s \oplus u}\}$，使用子集枚举，时间复杂度 $O(n 3^n)$。 [P9871 [NOIP2023] 天天爱打卡](https://www.luogu.com.cn/problem/P9871) 昨天那题的严格加强。思路大致相同，放几个实现细节。 首先不管离散化，由于有连续跑步限制，转移 $[j,i]$ 的跑步需要从 $dp_{j-2}$ 处转移。 而 $dp_{j-2}$ 可能是一个越界的下标，此时需要将其看作 $0$ 正常转移（因为你开始之前肯定没有跑过步）。 然后加上离散化之后，不能简单的从 $dp_{j-2}$ 进行转移，如果 $j-1$ 和 $j$ 在离散化之后的值不相邻，那么是需要从 $dp_{j-1}$ 转移的。 然后还要注意左端点与右端点在同一点的区间，转移的时候要考虑只跑这一天步的情况。 代码太难写了调死我了 /(ToT)/~~ ### 2024.09.17 [P7961 [NOIP2021] 数列](https://www.luogu.com.cn/problem/P7961) 今天 VP NOIp2021，一小时两题是我没想到的） 这个题目看着就很 DP 啊。既然要 DP 那肯定要先定好转移顺序，那我们就从小到大枚举当前填上什么值，可以填任意个，这样即可确保不重不漏。 发现低位会向高位进位，那么在填某一位时前面的位都已经确定了。因此我们枚举值的时候从低到高枚举即可。 填表法有些难搞，那么我们直接启动记搜！ ```cpp for(int i=0;i<=pos;++i){ int t=s+i; res+=((dfs(pos-i,num+(t&1),t/2,f+1)*C[pos][i])%P)*qpow(v[f],i)%P; res%=P; } ``` 状态是 `dfs(pos,num,s,f)`，表示还剩下 $pos$ 位没有填，当前已经确定有 $num$ 个 $1$，还未确定的部分为 $s$，当前填到 $f$ 的方案数。 这里的转移就是去枚举填上 $i$ 个 $f$，填上这一位后，$s$ 会变为 $s+i$，最后一位也确定了，我们将最后一位加给 $num$，$s+i$ 去掉最后一位即可。 非常好写，一下就过了。记搜大法好啊！ ### 2024.09.20 [P8803 [蓝桥杯 2022 国 B] 费用报销](https://www.luogu.com.cn/problem/P8803) 写了题解。在[这里](https://www.luogu.com.cn/article/f671ubwk)。 ### 2024.09.22 [P8810 [蓝桥杯 2022 国 C] 数组个数](https://www.luogu.com.cn/problem/P8810) 写了题解。在[这里](https://www.luogu.com.cn/article/w9qvrbj7)。