无尽之雨

· · 题解

提供一个和其他题解本质不同，且较为好写的做法！本文嵌套两层的下标会替换成括号，a 与 c 含义与题面一致。

记 h_i 表示前 i 个柜台中 -1 的个数，rk_i 表示前 i 种水果中，未被固定的水果种类数，r_i 表示 rk(a_i)。

记录 P_i 表示前 i 小的未出现过的水果的价格之和，m 为未出现过的水果数量。

考虑一个 \mathcal{O}(n^2) 的 dp：令 f_i 表示只考虑 1\sim i 这段前缀，且 a_i 这种水果被选取时的最大价值。

需要注意的是，并不是所有 f_i 都是有值的，f_i 是一个状态当且仅当：

转移考虑枚举前缀 j，f_i=\max\limits_j f_j + P(r_i) - P(\max(r_i-(h_i-h_j), r_j))+c(a_i)。从大到小枚举 j，枚举到第一个 j 使得 h_i-h_j\ge r_i-r_j 时，更新完 j 的贡献就得 break 了。

为什么会要 break？因为这时 a_j 成为了必选的水果，所有 j 之前的策略不一定能取到。

答案和 f 的转移类似，只是变成了 ans_i=\max\limits_j f_j + P(m) - P(\max(m-(h_i-h_j), r_j))。

于是我们写出了一个暴力 dp。

接下来考虑优化。

记录 G_j(s)=f_j-P(\max(r_j, h_j+s))，则我们可以改写 f 的转移方程式为 f_i=\max\limits_j G_j(r_i-h_i)+P(r_i)+c(a_i)。

注意到 G_j(s) 有决策单调性，也即若有 x<y，则 G_x(s)<G_y(s) 仅对一段前缀 s 成立。于是可以用二分栈优化决策单调性 dp。

单调栈中维护 (j, L, R)，表示 G_j 在 s\in [L, R] 的时候为最优选。

插入状态 j 的时候，会斩杀所有 s\le r_j-h_j 的 s（根据暴力 dp 的过程，这种 s 跑到 j 就截止了），剩下的 >s 的部分用一般的二分来维护单调栈即可。

Code，如果不理解如何单调栈可以参考代码，变量含义与题解一致。