P9871 [NOIP2023] 天天爱打卡

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

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

即 $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]$ 这一段区间全跑步的权值总和

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

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

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

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

对于一个线段，它产生贡献到一个更新上的前提是 $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)\})$

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

令 $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$ 即可

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

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