题解

思路

一张专辑中，只有严格大于该专辑此前所有歌曲的“前缀记录值”可能在某种播放顺序中贡献印象值。删除其余歌曲后，每张专辑变成严格递增序列 $b_1<b_2<\cdots<b_s$。

按末尾最大值 $b_s$ 从小到大处理专辑。设当前播放过的所有歌曲最大值小于 $b_j$，则播放这张专辑会由 $b_j,b_{j+1},\ldots,b_s$ 贡献 $s-j+1$ 点，并把最大值变为 $b_s$。因此

$$dp[b_s]=\max_j\left(\max_{x<b_j}dp[x]+s-j+1\right).$$

做法

子任务 1：枚举专辑排列

枚举全部专辑排列，按定义模拟歌曲播放并取最大值。

子任务 2：线性扫描前缀 DP

酷炫度不超过 $2000$ 时，用数组保存每个最大值对应的最优答案，每次直接扫描 $[0,b_j-1]$ 求前缀最大值。

子任务 3：Fenwick 树维护前缀最大值

用维护最大值的 Fenwick 树支持单点取最大更新和前缀最大查询。按专辑最大值排序后应用上述转移。

正确性证明

引理 1

删除专辑内不是前缀记录值的歌曲不会改变任何播放顺序的印象值。

证明：此类歌曲不大于同一专辑中更早的歌曲，因此播放到它时不可能严格超过全局历史最大值。证毕。

引理 2

存在一个最优播放顺序，其被采用的专辑按末尾最大值递增。

证明：若相邻两张被采用的专辑末尾最大值逆序，交换它们不会减少后者能贡献的记录值，且交换后全局最大值不增。反复交换即可得到递增顺序。证毕。

引理 3

处理末尾最大值为 $b_s$ 的专辑时，转移式枚举了该专辑在所有可能历史最大值下的最优贡献。

证明：若首个超过历史最大值的记录值是 $b_j$，恰有后缀的 $s-j+1$ 个记录值贡献；此前最优值必须来自某个 $x<b_j$，前缀最大查询恰取其中最大者。证毕。

定理

算法得到最大印象值。

证明：由引理 1 可只保留记录值；由引理 2 可按专辑末尾最大值处理；引理 3 的转移完整且无重复地覆盖最后选择每张专辑的所有情况。归纳可得所有状态最优，最终全局最大值即答案。证毕。

复杂度

设歌曲总数为 $S$，酷炫度上界为 $A$。时间复杂度 $O(S\log A+n\log n)$，空间复杂度 $O(S+A)$。