CF2062F

Prophesy_One · 2025-02-09 16:26:08 · 个人记录

这个东西有一种出题人脑子一热，一拍皮鼓想出来的东西。

首先这个形式并不好做 dp，考虑转化，令 x_i=\frac{a_i+b_i}{2},y_i=\frac{a_i-b_i}{2}，则 \max(a_i+b_j,a_j+b_i)=\max(x_i+y_i+x_j-y_j,x_j+y_j+x_i-y_i)=x_i+x_j+|y_i-y_j|。

然后直接按照 y_i 大小排序，做 dp 即可。