LibreOJ 10188 「HNOI2008」玩具装箱

萌新初学斜率优化~

首先设 sumi=i∑j=1cj。
有转移方程 fi=min0≤j<i(fj+(i−j−1+sumi−sumj−L)2)。

设 Ai=sumi+i,Bi=Ai+L+1，则原式变为 fi=min0≤j<i(fj+(Ai−Bj)2)。
考虑 0≤k<j<i，假设此时选 j 比选 k 更优，即 fj+(Ai−Bj)2≤fk+(Ai−Bk)2。
来推一波不等式： fj+(Ai−Bj)2≤fk+(Ai−Bk)2fj+A2i−2AiBj+B2j≤fk+A2i−2AiBk+B2kfj−2AiBj+B2j≤fk−2AiBk+B2k(fj+B2j)−(fk+B2k)≤2Ai(Bj−Bk)

注意到 ci 都是正整数，于是有 Bj>Bk。 (fj+B2j)−(fk+B2k)≤2Ai(Bj−Bk)(fj+B2j)−(fk+B2k)Bj−Bk≤2Ai

这玩意像什么？斜率！
我们在单调队列中维护一个下凸包（即相邻两点线段斜率单调上升的一个点集）。
然后每次从队头开始，在满足条件之前一直把队头扔掉（即我们刚才推出来的结论）。
这个时候的队头就是最优决策了（易证，其实是我懒）。
然后把当前的点入队，注意维护单调性。

这个方法没有几乎涉及到任何几何知识（斜率那些不算，就算你不知道也能看懂），纯粹是在代数层面推出的斜率优化，比较适宜新人理解。

代码：

#include <cstdio>
using namespace std;
const int N = 5e4;
int n,l,c[N + 5];
int q[N + 5],head,tail;
long long A[N + 5],B[N + 5],sum[N + 5],f[N + 5];
inline double slope(int x,int y)
{
    return (double)(f[x] + B[x] * B[x] - f[y] - B[y] * B[y]) / (B[x] - B[y]);
}
int main()
{
    scanf("%d%d",&n,&l);
    B[0] = l + 1;
    for(register int i = 1;i <= n;++i)
        scanf("%d",c + i),B[i] = (A[i] = (sum[i] = sum[i - 1] + c[i]) + i) + l + 1;
    q[head = tail = 1] = 0;
    for(register int i = 1;i <= n;++i)
    {
        for(;head < tail && slope(q[head],q[head + 1]) <= 2 * A[i];++head);
        f[i] = f[q[head]] + (A[i] - B[q[head]]) * (A[i] - B[q[head]]);
        for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],i);--tail);
        q[++tail] = i;
    }
    printf("%lld\n",f[n]);
}