斜率优化dp

斜率优化dp

斜率优化dp

斜率优化dp

直线的斜率是2*a[i],用一个已知斜率的直线去向上平移。当前面的线段不满足斜率大于2*a[i]时,是要淘汰的,因为截距不是最小的,直到碰到第一斜率大于2*a[i](一定的数值)的点,这个点(b[j],dp[j]+b[j]^2)使得dp[i]最小,

上一篇:传纸条


下一篇:918. 环形子数组的最大和