部分内容来自牛客相关课程课件 一些动态规划类型 树形 DP 树形 dp 的常用方法（例如树上背包）是将接下来要处理的儿子与以及处理完的儿子的全体进行合并，即把处理多个子树的问题转换为依次合并两个儿子的问题。 树形 dp 类型众多，故这里不多做赘述。 状压 DP 状压 dp 的核心是把状态用二进制数进行压缩（有些时候可能会用到四进制，如果一个点有三种…

题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包，每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个，我们需要这个答案序列先单调非降再单调非升，即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …

题目链接。 解析 后边的 dp 方式似乎和已有题解有一些差异。 首先考虑从第 $1$ 张纸片开始一张张放，计算出每张纸片有多少种放法，这分为三种情况： 最后局面该纸片占两格，显然只有 $1$ 种放法。 最后局面该纸片占一格，那么可能的放法有 $4$ 种，去除其中会覆盖最终局面的放法即可。 最后局面不存在该纸片，那么可能的放法为所有未被覆盖的位置的放…

题意 在左下角是 $(0,0)$，右上角是 $(W,H)$ 的网格上，有 $(W+1)\times (H+1)$ 个格点。 现在要在格点上找 $N$ 个不同的点，使得这些点在一条直线上。并且在这条直线上，相邻点之间的距离不小于 $D$。求方案数模 $10^9+7$。 解析 纯组合方法求方案数，是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 …

题意 题目链接。 给定 $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,…

题意 题目链接。 数轴上有若干传送门，初始是关闭或开启。对于关闭的传送门，经过后就会开启；对于开启的传送门，到达后会被传送到一个位置，然后会关闭。求从 $0$ 点走到 $x_n+1$，即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门，则记 $f_…

题意 题目链接 给定 $n$ 个点，求一个由若干个点连接成的凸多边形，所包含的点数最多，输出点数。 解析 先说解法：将所有边按照 atan2(y,x) 的值排序， 然后枚举凸多边形起点，再遍历排序后的边进行 dp 转移，复杂度为 $O(n^3)$。 大致思路与已有题解相同，但是我在这里想要阐述一个困惑我许久的点：为什么是 atan2 ？ 搜索百度百…

题意 题目链接 给出一个长度为 $m$ 的括号串，在其前后增添字符构造长度为 $n$ 的合法括号串，求方案数。满足 $n-m \le 2000$。 解析 容易发现这是一道 dp 且复杂度基于 $n-m$。 我们已知中间的那条括号串 $S$，需要构造出左边的 $P$ 和右边的 $Q$（当然也可能为空）。通过 dp 方程转移时，考虑需要满足的两个条件，…