见 这篇笔记 第0部分。

由于AcWing的LaTeX有点奇怪，所以文中所有应该用 {} 表示的minmax全部采用小括号

题目链接
怎么一上来就是紫题啊

题意

给定 $C_i$ 表示每个物体长度，把 $i\sim j$ 的物品放入一个容器中，容器的长度为 $x=j-i+\sum_{k=i}^j C_k.$ 一个长度为 $x$ 的容器制作费用为 $(x-L)^2$ ，求装下所有物品的最小费用。

思路

设 $S[n]=\sum( C_i+1),f[i]$ 为装好前 $i$ 个的最小花费，转移方程为 ：
$$ f[i]=min(f[j]+(S[i]-S[j]-1-L)^2). $$
将 $L$ 提前加一，去掉 $min$ 化简得：
$$ f[i]=f[j]+(S[i]-S[j]-L)^2 $$
把平方拆开得到：
$$ f[i]=S[i]^2-2S[i]L+f[j]+(S[j]+L)^2-2S[i]S[j] $$

下面将描述如何进行斜率优化。

斜率优化的一般方式

注：此处对应讲解的“线性规划”部分，个人认为比较便于理解。

对于上面那个式子，进行移项，使得变成形如 $y=kx+b$ 的形式。

移项遵循原则：把含有 $g(i)\times g(j)$ 的表达式看做斜率 $k$ 乘以未知数 $x$ ，含有 $f[i]$ 的项必须在 $b$ 的表达式中，含有 $g(j)$ 的项必须在 $y$ 的表达式中。为了方便分析，如果 $x$ 的表达式单调递减，等式两边同乘 $-1$ 变为单增。

那么原式就可以化为：
$$ 2(S[i])S[j]+(f[i]-S[i]^2+2S[i]L)=(f[j]+(S[j]+L)^2) $$
其中，一次函数的各个项分别对应：
$$ k_i=2S[i],x_i=S[j],b_i=f[i]-S[i]^2+2S[i]L,y_i=f[j]+(S[j]+L)^2 $$
对于这个式子，我们的目的是求出一个 $j$ 使得 $f[i]$ 最小，又有 $b[i]=f[i]-S[i]^2$ ，所以从图像角度看，就是找某个点使得这条直线经过它的时候算出来的 $b$ 最小。

由上面的式子可以知道，这条直线的斜率是固定的。那么想象在一个平面上，有一些点，一条直线向上移，碰到的第一个点一定是使得 $b$ 最小的位置。 可以发现，可能的点位于点集的下凸包上。

那么现在只需要考虑如何维护凸包点集即可。

用单调队列维护:

(1) 在凸包上找到最优点 $j$ ,并用来更新 $f[i]$

(2) 将 $i$ 作为一个决策点加入，并更新凸包（如果点 $i$ 也是决策点之一，那么交换顺序）。具体操作为，（对于下凸包）如果 $(q[t-1],q[t])$ 的斜率不大于 $(q[t],i)$ 的斜率，那么队尾出队，出队完成后把 $i$ 加入。
slope(q[t-1],q[t])>=slope(q[t-1],i) （这个地方讲义里面貌似有误，和下凸包的情况不符）

决策单调性再优化

Warning ：此部分需要证明，并非通用。

设 $j_0[i]$ 为 $f[i]$ 转移的最优决策点，那么有 $\forall i\leq i’,j_0[i]\leq j_0[i’]$ （非严格递增）（证明略，见文末讲义）

考虑如何证明。此题中 $k_0[i]=2S[i]$ 显然单增。详细一点就是：$k_0[i]$ 单增，最优决策点单增（看下凸包的图）。当然如果不敢肯定的话还是老老实实二分栈吧qwq

由于最优决策点递增，那么可以用单调队列维护。在原先找 $j$ 的过程中，是从队头一个一个找（或者二分）的，现在就改为：
如果队头线段斜率 $\leq k_0[i]$ 直接出队，停止时即为最优决策点。

复杂度 $O(nlogn)=>O(n)$

代码

#include <bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;
const int N=5e4+10;
ll n,L,h=1,t=0,q[N],s[N],f[N];
ll X( ll num ) { return s[num]; }
ll Y( ll num ) { return f[num]+(s[num]+L)*(s[num]+L); }
lb slope( ll n1,ll n2 ) { return (lb)(Y(n2)-Y(n1))/(X(n2)-X(n1)); }

int main()
{
        scanf( "%lld%lld",&n,&L ); L++; s[0]=0;
        for ( int i=1; i<=n ;i++ )
                scanf( "%lld",&s[i] ),s[i]+=s[i-1]+1;

        q[++t]=0;
        for ( int i=1; i<=n; i++ )
        {
                while ( h<t && slope(q[h],q[h+1])<=2*s[i] ) h++;
                f[i]=f[q[h]]+(s[i]-s[q[h]]-L)*(s[i]-s[q[h]]-L);
                while ( h<t && slope(q[t-1],q[t])>=slope(q[t-1],i) ) t--;
                q[++t]=i;
        }

        printf( "%lld",f[n] );
}