作者:滴答滴答箫雨伞_335 | 来源:互联网 | 2023-05-17 07:31
APIO2010特别行动队$$\frac{f_j+a\timessum_j^2+b\timessum_jf_ka\timessum_k^2b\timessum_k}{sum_jsu
APIO2010 特别行动队
\[\frac{f_j+a\times sum_j^2+b\times sum_j-f_k-a\times sum_k^2-b\times sum_k}{sum_j-sum_k} >2asum_x
\]
转移点 \(j,k\) ,当前点 \(x\) ,右侧是单调降的
如果 \(j>k\) 且上式成立,则 \(j\) 比 \(k\) 优
元素关系单调降的单调队列(即一个上凸壳)
弹栈:
如果队首的两个点的斜率大于 \(2asum_x\),就弹
队尾就是满足单调降就好了
ZJOI2007 仓库建设
\(f_x=(\min\limits^{x-1}_ {i=1} f_i-s1_i\times dis_y+s2_i)+s1_y\times dis_y-s2_y\)
其中:
\[s1_x=\sum ^{x}_ {i=1}p_i\ \ \ \ s2_x=\sum_{i=1}^x p_i\times dis_i
\]
如果 \(i 且
\[\frac{f_i-f_j+s2_i-s2_j}{s1_i-s1_j}>dis_x
\]
\(i\) 点则不优
右边是单调增的,所以是个下凸壳
[USACO08MAR]Land Acquisition G
首先用排序把矩形留下有用的部分
然后元素是满足 \(x\) 单调减,\(y\) 单调增
然后就可以斜率优化了
\[\frac{f_j-f_k}{x_{k+1}-x_{j+1}}>y_i
\]
右面是单调增的,维护下凸壳即可
斜率优化选做