题解：P13530 [OOI 2023] Music Festival / 音乐节

· · 题解

P13530 [OOI 2023] Music Festival / 音乐节

由于专辑内部的播放顺序不能改变，一张专辑中只有严格大于它前面所有歌曲的歌才可能贡献印象值，我们可以将每张专辑精简为一个严格单调递增的序列。

为了获得最大的印象值，我们需要尽量让最大值较小的专辑先播放，因此，我们将精简后的所有专辑按其最大值升序排列。

设 f_{v} 表示当前听过的所有歌中，最大炫酷度为 v 时，能获得的最大印象值。

有转移：

f_{a_{i,k_i}} = \max_{0\le j<k_i}\left(\max_{a_{i,j-1}\le t\le a_{i,j}-1}(f_t)+k_i-j\right)

线段树维护区间 \max 优化即可。

其中，\max_{a_{i,j-1}\le t\le a_{i,j}-1}(f_t) 在外层 \max_{0\le j<k_i} 内等价于 \max_{0\le t\le a_{i,j}-1}(f_t)，因为如果 f_t 在 [0,a_{i,j-1}) 时取得最大值，外层循环在枚举更小的索引 j-h 时，算出的总收益 f_t + k_i - (j-h) 必然大于枚举 j 时的 f_t + k_i - j，外层的 \max 会自动选择更小的索引，从而屏蔽掉了越界带来的误差。

而 \max_{0\le t\le a_{i,j}-1}(f_t) 可以用树状数组维护前缀 \max 优化，代码更简单且常数更小。

时间复杂度 O((\sum k_i) \log V)。