题解：AT_joisc2019_e ふたつの料理 (Two Dishes)

一只绝帆 · 2025-02-19 19:29:48 · 题解

显然有暴力 \rm dp：f_{i,j} 表示第一个序列进度是 i，第二个序列进度是 j，显然我们知道这个状态的时刻是 suma_i+sumb_j。

二维 \rm dp 考虑扫描线一维变成整体 \rm dp，每次 f_{i-1}\to f_i 的时候我们会进行前缀加，并把若干个 j-1\to j 的转移系数 v_j 变成 0，然后从左往右进行转移。

考虑动态维护 d_j=f_j-f_{j-1}-v_j，显然 d_j\ge 0，否则就会触发 v_j 的转移。

考虑仅仅变化一个 v_j 造成的影响：

• 若 v_j\ge 0，那么将其置为 0 后 d_j 会变大，并且由于转移变得更不优了，不会触发转移。

• 若 v_j<0，那么置为 0 后 d_j 会变小，转移变得更优了会立刻触发转移，造成的效果是操作前从 j 往后找一个最短的前缀使得 \sum_{k\in[l,r]}d_k\ge |v_j|，然后将 [l,r-1] 的 d 清空，将 r 的 d 减去 |v_j|-\sum_{k\in[l,r)}d_k，手模可以理解这个结论。

同样的，考虑仅仅进行前缀加（对前缀 j 加 x）造成的影响：

• 若加了正数，则前缀 j 内部没有任何新的转移，这个过程后若 d_{j+1}<0，则我们需要仿照上一部分进行 v 的转移。

• 若加了负数，我们把前缀加变成对差分数组的改变，也就是全局减和后缀加，此时一个关键的问题是：所谓的全局减，要不要仿照上一个后缀减那样，对差分数组处理？

  • 答案当然是不！从事实意义来考虑，我们对差分数组的处理是进行了 v_j 的转移，而事实上我们对全局（或者说前缀）进行减，并不会导致前缀内部或外部产生相邻之间的转移。

  • 从抽象的角度来说，我们一定要在这个全局减和上面的后缀减之间找到一个不同点，那就是全局减改变的是 d_0，f_{-1} 作为没有意义的值应当是 -\infty，所以 d_0=+\infty，在此约束下我们进行上文的过程就是正确的。

现在的问题是，我们即将同时变化多个 v_j，有正有负，还要进行一个前缀加，在 \rm dp 中这些“事件”的时刻都是同时发生的，那么我们自然要问：是多次做上面这个过程吗？按照什么顺序做？

事实上每个操作只会影响后缀，且与前缀无关，所以要想它们同时执行，从后往前做即可。

code。