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

题意 题目链接。 有 $n$​ 行 $m+1$​ 列格点，第 $1$​ 列和第 $2$​ 列格点之间有 $e$ 条边，第 $i$ 条边的边权为 $c_i$，保证联通。第 $i$ 与 $i+1$ 列中的边是由第 $1$ 列和第 $2$ 列的边复制得到的。对于前 $i$ 列（$2 \le i \le m+1$），求对于前 $i$ 列的点与端点都在前 $…

题意 题目链接。 有两组物品，每个物品都有一定的价值，你需要选择若干个物品，收益为两组物品中价值和较少的那组物品的价值和减去所选取的所有物品数。使收益最大化。 解析 发现肯定优先选择价值高的物品。 发现如果已经选择了若干个物品，接下来那个物品只有选择当前总价值低的那一组才有可能有更优解。 由上，本题可以用双指针解决。对于两组物品分别用一个指针维护，…

引用/参考：绍兴一中相关课件，Acfboy 的博客。 决策单调性 决策单调性指的是 dp 的决策时的最优位置是单调的。 常见地，若存在： $dp_i = f(dp_j)$ 中，$i$ 的决策位置是 $pos_i$，那么对于所有 $i\ge2,pos_i \ge pos_{i-1}$。 难点在于观察(猜)出其为决策单调，经常可以不证明。一般通过打表观…

题意 题目链接。 给出一颗树，走到叶子节点后可以回到它的第 $k$ 祖先，求最多可以访问多少叶子节点。 解析 定义 $f_{i}$ 为从 $i$ 节点开始走，最后走回到 $i$ 节点的贡献，$g_i$ 为从 $i$ 节点开始走，最后不用回到 $i$ 节点的最大贡献。 先预处理出从每个点开始走可以回到的最高点，对于叶子节点，初始先将其贡献打到其第 $…

题意 题目链接。 $n\times m$ 的场地上存在一些箱子，碰到了就会被推动，不可以使任何箱子被推出场地。求从 $(1,1)$ 走到 $(n,m)$ 的方案数。 解析 发现该问题类似于过河卒，考虑 dp。由于向右和向下移动所涉及的箱子不同，且如果越过了箱子就一定不会再次推到（不能往回走），考虑如下设置状态： 记 $f_{i,j}$ 为从上方走到…

题意 题目链接。 给定一个序列，每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。 解析 给出一种该题题解区中都没有提到的做法：整体二分。 对于整个区间按照值域进行二分，初始值域为负极大值到正极大值，每次二分都找出 $mid$ 值的分界线，然后对于左右两个区间依次二分。由于分界线左侧的那个…

题目链接。 题意不多赘述。 解析 由于每次会将石子最多的那堆的序号加入 $S$ 中，我们考虑将原始的石子堆从大到小排序。首先我们发现如果有一堆比其他都要高，我们可以将他取到与第二高的一样高，这样的话结果只可能会更优（因为相同时优先取小的）。 依照这个思路，我们考虑按照高度一层一层取下来，这样答案会越来越优（若存在多个高度相同的，你只需要认为在取的过…

题意 题目链接。 给定一个序列，包含 $n$ 个有重量和价值的物品。需要找出一个连续区间，可以选择其中的至多 $w$ 个物品令其重量减半（向上取整）而价值不变，然后该区间重量和须不大于 $k$。求满足这样条件的总价值最大的区间。 解析 求区间最大价值容易想到双指针。考虑如何维护重量减半（以下简称打折）的 $w$ 个物品。 由于元素会有重复，考虑用两…