题目链接


一、思路解析

首先来看题目的询问内容。题目要求小$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$)而言太大了。

“水题”链接:Luogu P1026 统计单词个数
本来是道水题,结果因为各种各样奇葩的错误,写了整整一天,WA2次,2次下载样例才AC。。。
考点是DP,结果早上花了1个多小时,字符串处理还没写完——20分钟写完带BUG的字符串预处理,20分钟用来把本来写对了的函数改出BUG,再花20分钟修正这个BUG。。。心态血崩。

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


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

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

这几天学DP学得有一定的心得,便来写一发学习笔记。知道自己get到的只不过是DP的一点点皮毛,所以希望自己以后能学习到更多的有用的知识。

星期二上课时教练说要讲DFS,当时就在想:DFS上个学期不是讲函数递归时不就讲过了吗???为什么还要再讲一遍?
认认真真地学了,写了5,6个小时的DFS(由于我们都是蒟蒻,没有学剪枝,因此写不了过难的题),看看天,要下雨了。难道今天就要把时间全耗在简单DFS上,一点提升都没有了吗?