P9871 [NOIP2023] 天天爱打卡

· · 个人记录

好像没有什么可以一语中的的分析方法，但是各个key point之间总是会卡住

初见思路

考虑到有 k 和 n 两个维度的限制，可以直接开一个 n^2 状态 n 转移的 O(n^3) dp

Key Point 1

发现 k 只要断一次就得从头开始重新计数了，中间升高的部分可以考虑现算，直接把维度 k 拍扁，过程中现算

即 f(i) 为考虑前 i 天，第 i 天不跑的最大能量值

转移则有

f(i)=\max(f(i-1),\max_{i-k-1\le j \le i-1}\{f(j)-d(i-j)+w(j,i-1)\})

其中 w(j,i-1) 是 [j,i-1] 这一段区间全跑步的权值总和

Key Point 2

最初认为奖励 (x,y,w) 的限制中， y 是很麻烦的东西，当时直接考虑把 (x,y) 画到平面上，发现要查询的范围是一块三角形，非常难做

但是连跑 y 天，那就是说跑到当前点时，有一个最大的可以满足的起点，从那个点开始前面的所有点都满足要求

但是事实上题目里已经很明显了，要求从x+y-1这个位置开始跑到现在，那么就可以考虑把它看作一个区间，只有跑步的区间覆盖了这个区间就能得到对应的权值

而对于 f(i) ，枚举转移到它的位置 f(j) ，其中要连续跑的区间就是 [j,i-1] ，此时就会发现变成了一个二位偏序问题，dp的过程中用扫描线维护对应要查询的值

Key Point 3

对于一个线段，它产生贡献到一个更新上的前提是 x-y+1\ge l \;and\;x\le r

在更新的过程中，因为是从左往右按时间轴正向走的，所以 r 单调递增，那么每次产生贡献就只和当前查询的左端点有关，只要 l\le x-y+1 就能造成贡献，所以可以直接区间加扔到对应的状态位置上，就不需要专门扫描线去处理它们的贡献了

于是，令 f(i) 为覆盖完后续线段贡献后的答案（注意是在更新过程中不断变化的，但是在当前这个位置更新出来的答案是没有问题的，最后答案只要找 f(n+1) ）

那么转移(忽略后来叠上去的线段贡献修改)就有

f(i)=\max(f(i-1),\max_{i-k-1\le j \le i-1}\{f(j)-d(i-j)\})

Key Point 4

之前已经要求了一个区间加的操作，发现此时状态更新时来的状态也是一个区间

考虑整个dp用线段树维护，但是中间的 d(i-j) 比较烦，提出来，考虑直接变成线段树上维护的值

令 g(i) 为线段树上维护的值， g(i)=f(i)-d\cdot i

那么转移就有

g(i)=\max(g(i-1)+d,\max_{i-k-1\le j \le i-1}\{g(j)\})

最后统计答案要用到dp值的时候直接看 g(i)+d\cdot i 即可

Key Point 5

离散化是显然的，但是不知道为什么这一次理解需要的点数是 O(m) 而不是 O(mk) 居然有点障碍

发现在状态转移时向左找决策点的过程中，除非遇到区间端点，否则从线段中得来的收益是不会改变的，而实际收益只从线段中来，所有不在线段端点上的点都是会更劣的，所以可以直接只存区间端点