使用斜率优化是有条件的，在k（i）*g(j)把k(i)作斜率，g（j）横轴，必须保证都是单调递增的，如果不是就要通过添加负号改变单调性

J. 玩具装箱

题目描述

原题来自：HNOI 2008

P 教授要去看奥运，但是他舍不得他的玩具，于是他决定把所有的玩具运到北京。

他使用自己的压缩器进行压缩。这个压缩器可以将任意物品变成一维，再放到一种特殊的一维容器中。P 教授有编号为  的  件玩具，玩具经过压缩后会变成一维，第  件件玩具压缩后长度为 。

为了方便整理，P 教授要求：

• 在一个一维容器中，玩具的编号是连续的；
• 如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果要将  号玩具到  号玩具  放到同一个容器中，则容器长度不小于 。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 ，其制作费用为 ，其中  是一个常量。

P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 。试求最小费用。

输入格式

第一行输入两个整数 ；
接下来  行，每行一个整数 。

输出格式

输出最小费用。

这种和区间划分有关的dp很容易列出dp方程f[i]=min(f[j]+(sum[i]+i---1-sum[j]-j)^2)

鐜式子化简，把和ij都有关的部分提出来，i部分作为斜率，横坐标是j部分，纵坐标就是只和j有关的部分，截距就是i点的最优决策

最大值，维护上凸包，在i决策前维护k最逼近的值，决策后把i放入维护斜率单调递减

const int N=100000+10;
int n,l;
ll sum[N],dp[N];
int head,tail,q[N];
inline double slope(int i,int j)
{
return ((dp[i]+(sum[i]+i)*(sum[i]+i))-dp[j]-(sum[j]+j)*(sum[j]+j))/(sum[i]+i-sum[j]-j);
}
int main()
{
n=re(),l=re();
_f(i,1,n)
{
scanf("%lldf",&sum[i]);
sum[i]+=sum[i-1];
}
head=tail=1;
_f(i,1,n)
{
while(head
dp[i]=dp[q[head]]+(sum[i]+i-sum[q[head]]-q[head]-1-l)*(sum[i]+i-sum[q[head]]-q[head]-1-l);
while(head
q[++tail]=i;
}
chu("%lld",dp[n]);
return 0;
}