P9871 [NOIP2023] 天天爱打卡

P9871 [NOIP2023] 天天爱打卡

经典dp+线段树优化+离散化

前两个步骤略讲，主要是离散化。

首先考虑dp，朴素的，容易写出状态 \(f_i\) 表示考虑到第 \(i\) 个位置，且强制第 \(i\) 天跑步的最大能量值。

考虑枚举最后一段跑步的时间，有

\(f_i=\max(\max\limits_{k<j}f_k-(i-j)\times d+\sum\limits_{j<l_p\le r_p\le i}v_p)\)

不妨设 \(g_i=\max\limits_{j<i}f_i\)，再自然的参变分离，有

\(f_i=\max(g_j+j\times d+\sum\limits_{j<l_p\le r_p\le i}v_p)-i\times d\)

容易看出只需要维护前面的最大值即可。考虑线段树优化。对于 \(g_j+j\times d\) 是定值，直接在线段树末尾插入即可。后面的部分可以在枚举的过程中不断把 \(r_p=i\) 的线段加入，也就是线段树上区间加。具体的说，对于每一个 \([l_i,r_i]\)，给所有 \(j<l_i\) 加入 \(v_i\)，表示若走满 \([j+1,i]\) 可以取到该线段。

这就是前面的部分，复杂度为 \(O(n\log n)\)。

考虑优化。首先数据范围显然想让我们把复杂度降到 \(O(m\log m)\)。于是我们就观察到 \(f\) 序列会分成很多段。

这些线段的左右端点把整个序列分为多段，观察每一段的决策，对于 \([l,r]\) 段，一定只有都跑和都不跑两种情况。考虑选每段的右端点作为该段的代表元。于是对于每个线段，我们只保留 \(l_i-1\) 与 \(r_i\) 两个端点即可，离散化完之后转移同样。

复杂度 \(O(m\log m)\)。