两道利用单调性优化DP的题。
跳房子
分析
- 意识到金币越多能收集的最大分数必定越多，又因为题目需要求解满足要求的最小金币，故要想到二分。
- 要检验二分中每次mid的金币是否符合要求（即check操作），首先贪心不可行；又因为我们check的本质是在给定金币限制的情况下要收集最大分数，而不是记录路径什么的（这要用搜索），因此我们考虑到用DP
- 首先尝试定义状态，我们先用最直白的思路，定义f[i]表示到第i个格子时搜集的最大分数量，发现可以从f[j]转移过来（j<i且需要j到i的距离正好合适），且满足最优子结构，也无后效性，故这种定义可行，转移方程可以写出。
- 这样我们将拿到数据弱的部分分，然后尝试思考时间复杂度优化，我们必须从DP（On方的复杂度）入手
- DP优化有几种方法，我们先对DP进行分析。首先DP方程本质是求满足条件的f[j]的最大值，就是说，对于给定的i，如果我们能马上锁定符合条件的j们，那么我们只需要找到他们中的最大值即可（f[i]=max(f[j]+i格子的分数）
- 因为我们无法马上锁定符合条件的j们，所以在朴素算法中我们选择枚举j，那么我们必须也只能选择省去j的for循环。这里我们尝试单调队列优化是否可行，因为我们模糊感觉这似乎是个求动态局部最值的问题（我们用到了max(f[j])，且j有和i的距离限制）
- 设机器人初始跳跃d格，花费了k金币，则满足条件为(d-k<=i到j的距离<=d+k)，我们注意到d,k是不变的，变的只有距离。随着i逐渐增大，与接近原点的的j渐行渐远，这些j就要被抛弃（因为两者距离大于d+k了）；但是随着i增大，有更多的离最新的i更近的j被解锁（注意到超过i的j，及离i太近的j是不合法的，此时两者的距离还小于d-k）。我们对此抽象一下，不断有旧的元素被淘汰，新的元素被注入，我们要寻找（维护）的就是当前时刻仍然有效的元素的最值，这就是单调队列没错了。
1.怎么定义状态？因为我必须要知道该次跳跃的距离和上次跳跃的距离（为了比较），我可以记f[i][j]为最后一次跳跃为从i到j的最值。
这次如果i表示已经来到了第i个平台会怎样？不行，因为虽然都是到达这个平台，但是路径不一样导致上次跳跃的距离不一样。又不可能把跳跃的距离存起来，那就存跳跃的两个端点了（表示状态）。转移方程：f[i][j]=max(f[i][j],f[k][i]+s[j])
这样就完成朴素On立方的算法了，当然需要优化
2.下一步尝试优化
因为是for i,for j,for k的三重循环，发现对于每个固定的i，只是更改终点j，那么有的f[k][i]的结果是可以一直重复用的，突破口应该在这里。（事实上，如何发现这个突破口，并进行下述的延伸找出j和k的关系是什么是最难想到的，我现在还无法解释这里的思维过程）
当然f[k][i]是否合法是受j的限制的（准确的说，是受i和j距离的限制，但是i是暂时不动的），显然k越靠近i，f[k][i]合法的可能性越大。但同时，当j越来越大时，原本不合法的k可能就会合法了，如下面符号构成的小图，随着j向右走，不断会有更靠左边的合法的k出现。
<--k i j-->
现在有个好消息，我们发现原先合法的k仍然合法。这就是本体与传统单调队列优化DP的题的最大区别：本题合法的元素有增无减，这意味着如果有个符合要求的f[k][i]是当之无愧的最大值maxx，那么maxx就会一直固定下来。所以我们不需要维护单调队列，只需随着j增加更新最大值即可。当j循环结束，k的合法性也向左蔓延到了最远处（在i未移动的前提下）。