标签: dp

9 篇文章

【整理】算法竞赛动态规划学习笔记
一些动态规划类型 树形 DP 树形 dp 的常用方法(例如树上背包)是将接下来要处理的儿子与以及处理完的儿子的全体进行合并,即把处理多个子树的问题转换为依次合并两个儿子的问题。 树形 dp 类型众多,故这里不多做赘述。 状压 DP 状压 dp 的核心是把状态用二进制数进行压缩(有些时候可能会用到四进制,如果一个点有三种或四种状态)。处理状压 dp …
牛客练习赛123 D 智乃想考一道完全背包(Hard version) 题解
题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包,每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个,我们需要这个答案序列先单调非降再单调非升,即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …
Codechef Starters 126 Uncommon Cycles 题解
题意 题目链接。 给你一棵树,你可以在树上连两条边,这两条边会分别形成两个环,要求这两个环没有任何相同的边或结点,求连边的方案数。 解析 蛮有趣的一个树形 dp。 考虑对于所有的连边方案,在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ,有多少方案是以其为 LCA 的,发现共有以下几种情况: $2-2$ 结构:在 $u$ 的两棵不…
P7716 「EZEC-10」Covering 题解
题目链接。 解析 后边的 dp 方式似乎和已有题解有一些差异。 首先考虑从第 $1$ 张纸片开始一张张放,计算出每张纸片有多少种放法,这分为三种情况: 最后局面该纸片占两格,显然只有 $1$ 种放法。 最后局面该纸片占一格,那么可能的放法有 $4$ 种,去除其中会覆盖最终局面的放法即可。 最后局面不存在该纸片,那么可能的放法为所有未被覆盖的位置的放…
2021牛客提高第二场 B.方格计数 题解
题意 在左下角是 $(0,0)$,右上角是 $(W,H)$ 的网格上,有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点,使得这些点在一条直线上。并且在这条直线上,相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数,是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …
CF1557D Ezzat and Grid 题解
题意 题目链接。 给定 $n$ 行 01 串,其中有 $m$ 个区间为 $1$​。删除若干 01 串使剩余串美丽,若干条 01 串美丽当且仅当任意相邻两个 01 串至少有相同的一位均为 $1$。 $n,m\le 3\times10^5$。 解析 考虑记 $f_i$ 为以第 $i$ 串结尾的最长美丽串的长度。发现 $f_i=f_j+1,j\in[1,…
CF1552F Telepanting 题解
题意 题目链接。 数轴上有若干传送门,初始是关闭或开启。对于关闭的传送门,经过后就会开启;对于开启的传送门,到达后会被传送到一个位置,然后会关闭。求从 $0$ 点走到 $x_n+1$,即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门,则记 $f_…
CF1065F Up and Down the Tree 题解
题意 题目链接。 给出一颗树,走到叶子节点后可以回到它的第 $k$ 祖先,求最多可以访问多少叶子节点。 解析 定义 $f_{i}$ 为从 $i$ 节点开始走,最后走回到 $i$ 节点的贡献,$g_i$ 为从 $i$ 节点开始走,最后不用回到 $i$ 节点的最大贡献。 先预处理出从每个点开始走可以回到的最高点,对于叶子节点,初始先将其贡献打到其第 $…
CF1225E Rock Is Push 题解
题意 题目链接。 $n\times m$ 的场地上存在一些箱子,碰到了就会被推动,不可以使任何箱子被推出场地。求从 $(1,1)$ 走到 $(n,m)$ 的方案数。 解析 发现该问题类似于过河卒,考虑 dp。由于向右和向下移动所涉及的箱子不同,且如果越过了箱子就一定不会再次推到(不能往回走),考虑如下设置状态: 记 $f_{i,j}$ 为从上方走到…