NOIP2024集训Day36 DP优化

NOIP2024集训Day36 DP优化

A. [NOIP2023] 天天爱打卡

前段时间才看过这道题。dp + 线段树优化 + 离散化。经典。

考虑朴素 dp。定义 \(f_i\) 表示考虑到第 \(i\) 个位置，并钦定第 \(i\) 天跑步的最大能量值。

枚举最后一段跑步时间，有：\(f_i = \max(\max\limits_{k\lt j} f_k - (i - j) \times d + \sum\limits_{j\lt l_p \le r_p \le i} v_p)\)。

假设 \(g_i = \max\limits_{j\lt i} f_i\)，参变分离，有：\(f_i = \max(g_j + j\times d + \sum\limits_{j\lt 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\lt l_i\) 加入 \(v_i\)，表示若走满 \([j + 1, i]\) 可以取到该线段。

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

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