洛谷4565 [CTSC2018]暴力写挂
LuoguLOJ分析题目中的式子等价于我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。代码// ===============================...
标签 动态规划 下的文章
- 首页
- 动态规划
CF932F Escape Through Leaf
CodeforcesLuogu分析容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑...
洛谷6622 [省选联考 2020 A/B 卷] 信号传递
LuoguLOJ分析考虑从 $x$ 传递到 $ y$ 的代价，显然有这样子就可以 $\mathcal{O}(m2^m)$ 预处理 $g(x,S)$ 和求 $f_S$，总时间复杂度 $\mathcal{O}(m2^m)$。然而存 $g$ 需要 736MB 空间，并开不下。但是可以发现，我们只需要求 $x\in S$ 的 $g(x,S)$，所以我们只需要对每个 $x$ 求 $2^{m-1}$ 个...
洛谷3757 [CQOI2017]老C的键盘
LuoguLOJ分析为什么 17 年省选还出 13 年的题的弱化版啊设 $dp_{u,i}$ 表示以 $u$ 为根的子树，$u$ 的排名为 $i$ 的方案数。转移时将 $v$ 合并到 $u$ 中，在 $i+j-1$ 个比 $u$ 小的数中选出 $j$ 个放在 $v$ 子树中，在 $sz_u+sz_v-i-j$ 个比 $u$ 大的数中选出 $sz_v-j$ 个放在 $v$ 子树中，即乘上两个组...
CF149D Coloring Brackets
CodeforcesLuogu分析设 $dp_{l,r,0/1/2,0/1/2}$ 表示 $[l,r]$ 段，$l$ 没有颜色/红色/蓝色、$r$ 没有颜色/红色/蓝色的方案数。当 $r-l+1=2$ 时为边界，有 $dp_{l,r,1,0}=dp_{l,r,2,0}=dp_{l,r,0,1}=dp_{l,r,0,2}=1$。考虑转移。如果 $l,r$ 是一对匹配的括号，直接从 $dp_{l...
CF1316E Team Building
CodeforcesLuogu分析有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。然而 $p+k\leq n$，所以这个做法不太行。注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选为观众，改...
洛谷4654 [CEOI2017]Mousetrap
LuoguLOJ分析为了方便，将陷阱作为根节点。那么冷静分析一下可以得到一些结论（没有证明）当老鼠走到一个叶节点时，它将被困住。当老鼠被困住时，将其它岔路口堵住，然后将到根的路径擦干净是最优的。设 $f_u$ 表示老鼠进入 $u$ 子树后回到 $u$ 的最小操作次数。显然老鼠会找一个 $f$ 最大的子树进去，所以堵住 $f$ 最大的子树最优，此时老鼠会进入 $f$ 次大的子树，于是有这里减去...
洛谷4590 [TJOI2018]游园会
LuoguLOJ分析发现题目中那个 LCS 的限制不好处理，考虑建一个自动机来解决这个问题。假设我们已经建出了自动机，我们就可以设 $f_{i,j,k}$ 为前 $i$ 个字符，已经转移到自动机的 $j$ 节点，已经匹配到了 NOI 的第 $k$ 位的方案数，然后根据 $k$ 转移即可。现在考虑如何建这个自动机。考虑求两个串的 LCS 的过程，即设 $g_{i,j}$ 表示第一个串匹配到 $...
CF814E An unavoidable detour for home
CodeforcesLuogu分析显然对于合法的图，满足不在最短路树上边连接的点在同一层。设 $f_{i,j}$ 表示前 $i$ 个点，$[i-j+1,i]$ 中的点在同一层时的方案数，$g_{i,j,k}$ 表示这一层有 $i$ 个点，上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。$f$ 的转移不难得到：枚举上一层的...
洛谷3750 [六省联考2017]分手是祝愿
LuoguLOJ分析首先可以发现，$i$ 只能被 $\geq i$ 的开关操作掉。从而我们只需要从大到小模拟一遍，如果 $i$ 亮着就操作 $i$ 开关，就可以算出最小需要操作的次数 $c$ 了。这样子就可以拿到 $50$ 分（实际上有 80 分）。冷静分析一下可以发现，达到目标所需要按的开关组合是唯一确定的。我们把这些开关叫做正确的。考虑一个 DP。设 $dp_i$ 表示从剩余 $i$ 个...