CF995F Cowmpany Cowmpensation
CodeForces Luogu 分析 设 $dp_{i,j}$ 表示以 $i$ 为根的子树，$i$ 的权值为 $j$ 的方案数。容易得到转移 前缀和优化即可做到 $\mathcal{O}(D)$ 转移，总时间复杂度 $\mathcal{O}(nD)$。 考虑优化。可以发现，$dp_{1,x}$ 为关于 $x$ 的 $n$ 次多项式（可以理解为每个叶子节点都为一次式，往上合并时做乘法从而次...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
AGC033D Complexity
AtCoder Luogu 分析 首先能够想到设 $dp_{i,j,k,l}$ 为左上角为 $(i,j)$、右下角为 $(k,l)$ 的矩阵的凌乱度，然而显然是过不去的。 注意到答案在 $\log nm$ 级别，因此可以考虑设 $dp_{i,j,k,l}$ 为凌乱度为 $i$ 时，上界为 $j$ 下界为 $k$ 左界为 $l$ 的矩阵右界最远能到哪。根据横切和竖切的情况不难得到转移 如果暴...
51nod1850 抽卡大赛
51nod 分析 首先考虑一个暴力做法。 假设我们现在正在计算张三的期望收益。则根据期望的线性性，我们只需要求出张三抽到某一张卡时位于某一个排名的概率。 枚举张三抽到的卡（为了方便称这张卡为 A），然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个不是张三的人中有 $j$ 个抽到的卡比张三大的概率。设 $p$ 为第 $x$ 个不是张三的人抽到的卡比 A 大的概率，容易得到转移 这...
CF115E Linear Kingdom Races
Codeforces Luogu 分析 考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移 这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。 考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i...
洛谷5772 [JSOI2016]位运算
Luogu 分析 先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。 考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直...
洛谷5774 [JSOI2016]病毒感染
Luogu 分析 首先那个规定的意思是如果往左走就要把左边所有没治愈的村庄治愈。 可以发现整个过程可以划分成若干段，每段以任意顺序治愈后回到该段的起点，再治愈下一段。 考虑 DP。设 $dp_i$ 表示治愈前 $i$ 个村庄的最小死亡人数。记 $s$ 为 $a$ 的前缀和，$w_{i,j}$ 为从 $i$ 出发治愈 $[i,j]$ 中所有村庄再回到 $i$ 的最小死亡人数，容易得到转移 边...
洛谷5770 [JSOI2016]无界单词
Luogu 分析 容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。 第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到 第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$...
洛谷4323 [JSOI2016]独特的树叶
Luogu 分析 先考虑一个 $\mathcal{O}(n^2)$ 的做法。 先求出以每个节点为根，整棵树的哈希值。 然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。 这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。 异或满足可减性，很容易抵消掉。所以...
洛谷6096 [JSOI2015]地铁线路
Luogu 分析 第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。 第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。 假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d...
洛谷4228 榕树之心
Luogu LOJ 分析 我们先考虑怎么算根节点的答案。 先假设它只有两棵子树 $u$ 和 $v$，榕树之心在根节点处。 如果 $u$ 长出一个节点，$v$ 长出一个节点，那么榕树之心还在根节点处，相当于这两次操作抵消掉了。 那么我们只需要判断根节点的所有子树能否相互抵消掉。 注意每棵子树是可以自行抵消一部分的，因此可以设 $f_u$ 表示 $u$ 子树内最多可以自行抵消多少对。 考虑 $f...