专栏文章

CF2062F

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqarc1v
此快照首次捕获于
2025/12/04 01:44
3 个月前
此快照最后确认于
2025/12/04 01:44
3 个月前
查看原文
这个东西有一种出题人脑子一热,一拍皮鼓想出来的东西。
首先这个形式并不好做 dp,考虑转化,令 xi=ai+bi2,yi=aibi2x_i=\frac{a_i+b_i}{2},y_i=\frac{a_i-b_i}{2},则 max(ai+bj,aj+bi)=max(xi+yi+xjyj,xj+yj+xiyi)=xi+xj+yiyj\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|
然后直接按照 yiy_i 大小排序,做 dp 即可。

评论

0 条评论,欢迎与作者交流。

正在加载评论...