CF1007E Mini Metro
Codeforces 分析 orz yhx 为了方便我们在最后加一个 $a_i = N, b_i = N, c_i = +\infty$ 的站台，其中 $N$ 是一个很大的数。这样子我们可以保证每辆火车恰好送走 $k$ 个人。 设 $f_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ 时刻最少需要放多少辆火车，$g_{i, j}$ 表示只考虑前 $i$ 个站台、要坚持 $j$ ...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
洛谷5617 [MtOI2019]不可视境界线
Luogu 分析 首先考虑给你两个圆怎么算交的面积。 设两圆心距离为 $d$，可以算出交弦所对的圆心角 $\theta = 2\arccos \frac{d}{2r}$，然后两个扇形的面积为 $\theta r^2$、菱形的面积为 $\sin\theta r^2$，因此交面积为 $(\theta - \sin\theta)r^2$。 考虑 DP。设 $f_{i, j}$ 表示前 $i$ 个圆...
洛谷5292 [HNOI2019]校园旅行
Luogu LOJ 分析 orz myy 可以发现，一条回文路径左右扩展一个相同字符仍然是一条回文路径。 设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径，转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。 因为我们可以在一条边上反复横跳，所以直觉上这个东西只会和奇偶性有关。 对于连接同色点的边，我们对每个连通块单独考虑：如果构成二分图，则可以只保...
洛谷3724 [AHOI2017/HNOI2017]大佬
Luogu LOJ 分析 可以发现确保自己不死和攻击大佬是两个独立的行为。 于是我们可以先求出最多有多少天可以用来攻击大佬，只需要做一个简单的 DP 即可。设这个天数为 $t$。 考虑怼大佬的操作，我们实际上只关心能够发动它的天数以及它的伤害。于是我们可以 BFS 出所有这样的 $(d, F)$ 二元组。 接下来考虑如何能够打败一个自信值为 $c$ 的大佬。进行分类讨论： 不怼大佬，那么...
洛谷3214 [HNOI2011]卡农
Luogu 分析 首先题目中的集合是无序的，我们将其转为有序的来计算，只需要最后除以 $m!$ 即可。 设 $f_i$ 表示划分为 $i$ 个片段的方案数，考虑转移。 首先，如果我们已经确定了前 $i - 1$ 个片段，那么第 $i$ 个片段唯一确定，这样子的方案数为 $A_{2^n - 1}^{i - 1}$。 但是这样子会有一些不合法的情况： 第 $i$ 个片段为空：这样子去掉第 $i...
CF809D Hitchhiking in the Baltic States
Codeforces 分析 设 $f_{i, j}$ 表示前 $i$ 个数、LIS 长度为 $j$ 时末尾元素的最小值。 考虑转移。假设当前区间为 $[l, r]$，那么 不加：$f_{i, j} \gets f_{i - 1, j}$。 对于 $f_{i - 1, j -1} < l$，有 $f_{i, j} \gets l$。 对于 $l \leq f_{i - 1, j - 1...
LOJ3399 「2020-2021 集训队作业」Communication Network
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
洛谷2612 [ZJOI2012]波浪
Luogu 分析 考虑拆掉绝对值。对于一个数 $i$，如果它左右两边都比它小则其贡献为 $-2i$，如果一边比它小一边比它大则其贡献为 $0$，如果两边都比它大则其贡献为 $2i$。 考虑从小到大插入所有数。设 $f_{i, j, k, l}$ 表示插入了 $1 \sim i$，形成了 $j$ 个连续段，$1 \sim n$ 的贡献之和为 $k$，有 $l$ 个边界已经放了数的方案数。 这里...
洛谷5206 [WC2019]数树
Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 考察每个连通分量。一个大小为 $a$ 的连通分量会产生 $\frac{n^2 y}{1 - y} a^2$ 的乘积贡献，而 $a$...
CF183D T-shirt
Codeforces Luogu 分析 考虑对于每一件 T-shirt 计算其贡献。下面设当前考虑的 T-shirt 为 $k$。 设 $f_{i, j}$ 表示前 $i$ 个人，有 $j$ 人适合大小为 $k$ 的 T-shirt 的概率，转移为 是单减的。 因此我们可以每次贪心地找一个 $\Delta g$ 最大的 T-shirt 大小出来。 实现时，我们先求出对每个 T-shirt ...