最小得A>0
不理解斜率优化可以多画图
by 用户已注销 @ 2019-04-18 19:41:56
@[韩沛煊](/space/show?uid=47140) LZ可以看一下这个方程
~~~
[sum[i]=sigma(x1~xi)]
dp[j]+a*sum[j]^2=(2*a*sum[i]+b)*sum[j]-b*sum[i]-c-a*sum[i]^2+dp[i]
~~~
维护的点是 （sum[j],dp[j]+a*sum[j]^2）
横坐标单调递增，而纵坐标无单调性
很明显维护整个凸壳+二分
因为对于这条直线它的截距（与y轴的交点的纵坐标）就是dp[i]+常数，所以说dp取max或取min只是维护凸壳的方向不一样
比如取max时要求截距尽可能大，所以就维护上凸壳
取min时要求截距尽可能小，所以就维护下凸壳
至于$A>0$ @[fzszkl](/space/show?uid=23323) 按照这个方程来理解，反而更简单，纵坐标也单调，只需单调队列维护即可$0ω0$
不知道有没有帮到您QWQ
by Tommy_clas @ 2019-06-10 21:27:16