题解：P11027 [COTS 2020] 餐厅 Restoran
伊地知虹夏
·
·
题解
缝合怪。
首先考虑性质 A 怎么做。这就是 P1248 加工生产调度，结论是最优解满足 \forall 1 \le i < j \le n, \min(a_i,b_j) \le \min(a_j,b_i)。但是这个条件不满足传递性，所以分 a_i < b_i，a_i = b_i，a_i > b_i 讨论一下，得到排序方式。然后依次考虑每个人，记 p_i 为 a_i 的前缀和，q_i 为 [1,i] 的答案，则有 q_i = \max(q_{i-1}, p_i) + b_i。
然后考虑正解。先把所有人离线下来按照上述规则排序，记 {\rm rnk}_i 为 i 在新序列中的位置，那么方案就是将客人按照 \rm rnk 排序。
接下来我们要加速求答案的过程，考虑把 p_i，q_i 的转移写成 (\max,+) 卷积的形式：
[q_i, p_i] = [q_{i-1}, p_{i-1}] \times
\begin{bmatrix}
b_i & -\infin \\
a_i+b_i & a_i \\
\end{bmatrix}
我们使用线段树维护矩阵乘法即可。