题目链接


一、思路解析

首先来看题目的询问内容。题目要求小$R$至少获得$k$分的前提下花费的最小金币数。显然这是一个二分答案,因为当金币花少了以后,由于灵活性问题,分数达不到$k$,并且较大的花费带来的变化严格包含了较小花费带来的变化(即只会使结果变得更优,而不是更劣)。结果随着答案的变化呈现出不严格的单调性,所以考虑二分答案。
二分答案之后的验证就是一个典型的线性动态规划。设状态$dp_i$表示跳到格子$i$所能得到的最大得分。不难发现状态转移方程如下:
$$dp_i \; = \; \max\limits_{\max(1,d-v) \leq \; x_i - x_j \; \leq d + v} {dp_j}\;+\;s_i$$
可以用两层循环计算状态,但是时间复杂度为$O(n^2)$(算上二分过程则为$O(n^2 \log n)$),对于本题的数据范围($n \leq 5 \times 10^5$)而言太大了。

题目链接


一、思路解析

给出一棵树,要求按顺序走完给定的所有点,每移动一步就要给这次移动经过的点增加$1$的点权。求每一个点的最小点权。
显然这是一个树上差分的题目,因为树上两点之间有且仅有一条最短路。并且,只有每一步都走最短路,最终的答案才会是最优(树上两点间无论如何走,经过的边组成的边集一定包含最短路上的所有点)。

题目链接
耶耶耶!终于AC了一道省选题目耶!开心!
(然而并没有什么用)


下面进入正题。。
相信大家应该都能想到动态规划的计算方向吧:将点按照高度升序排序,再按照排序结果进行计算。因为只有这样,才能保证状态转移时前面的状态都已经计算过了。
那么本题解存在的意义是什么呢???
答案是:讲一个个人觉得很interesting的小 {技巧}(huá jī)。

题目链接
一道可爱的区间DP。。。
题目中有一个很容易证明,又很不容易被注意到,但是又很重要的点:最优解的每一步中已经修好的点恰好是连续的。
那怎么证明呢?很简单,去维修不在当前区间处的点时一定会经过一些点,反正维修不需要时间,那我们经过它们时何不“顺便”修好它们?早晚都是要修的,那还不如早点修完避免它们的花费一直上升。

新题解

感觉原来的题解代码写的实在是太丑了自己看了忍不住抽自己两巴掌,所以,在和同学一起限时($1h$,并没有写完)后决定重新写一下这篇题解。
没什么思维难度,就是模拟。妙用递归(每一层调用栈对应一层循环)可以大幅降低编程难度。同时,利用好标准库这个神器可以简化代码。具体的细节已经放在注释里了。