【Typical】【JZOJ 5378】 闷声刷大题

大题"/>

【Typical】【JZOJ 5378】 闷声刷大题

Description

给两个长度为N的序列A,B
要求形成k个A与B的匹配
A[i] $A[i]$匹配 B[j] $B[j]$条件为 i<=j $i<=j$
代价为 A[i]+B[j] $A[i]+B[j]$
A,B中每个元素至多匹配一次
最小化k个匹配的代价和
N<=15000,A[I],B[I]<=10^9

凸优化

首先sb dp是kn^2的，f[k][x][y]表示形成K个匹配A到x   B到y  的方案数
这时候，应该要觉察满分做法复杂度里这个K肯定是被削减的
考虑对于相同x,y，把k画成图像
f[k][x][y]有什么特性？它不仅是单调增的，而且还是凸的
你先在要求这个函数在k处的值，怎么办？
如果我们把函数略微旋转一定角度（实现中可以相当于整体加上一条直线，可以理解为对于A中每个元素减去一个常数C），f(k)一定能成为图中最低点
如果函数是凸的并有一个最低点，我们知道怎么求最低点处k的值
相当于消去k的影响，直接可撤销贪心就好
那你怎么知道旋转的角度？
二分咯。每次看最低点横坐标与k比较再调整角度就好了
复杂度n带log

注意了：这个方法只有在函数是凸的情况下才能用，所以才叫凸优化