【Luogu】P3195玩具装箱（斜率优化DP）

　　这题还是比较炫的

　　题目链接

　　我们设f[i]是已经装了前i个玩具，且第i个玩具是某箱子里装的最后一个东西（废话）

　　那我们很轻松可以想到一个转移方程

for(int i=;i<=n;++i)

    for(int j=;j<i;++j)

        f[i]=min(f[i],f[j]+squa(sum[i]-sum[j]+i-j--L)

　　其中sum是玩具长度的前缀和，squa是平方。

　　但是O(50000*50000)瞬间爆炸

　　我们设f[i]是由f[j]转移过来的，j是最优转移，同时还有一个不那么优的转移k

　　那肯定有\(f[j]+squa(sum[i]-sum[j]+i-j-1-L)<f[k]+squa(c[i]-c[k]+i-k-1-L)\)

　　我们设\(M=sum[i]-1-L,T[j]=sum[j]+j\)

　　容易发现M只和i有关，T只和j有关

　　然后\(f[j]+squa(M-T[j])<f[k]+squa(M-T[k])\)

　　两边平方和展开划一划得到

　　\(((f[j]+squa(T[j]))-(f[k]+squa(T[k])))/(2*(T[j]-T[k]))>M\)

　　注意到f,T,M都是单调的

　　于是可以单调队列斜率优化

　　为什么是斜率优化呢？因为左面那个大于M的东西看着像斜率啊

　　233

　　附上一个讲斜率优化的博客

　　yybyyb

　　代码

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<algorithm>

#include<iostream>

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long f[];

long long M[];

long long T[];

long long c[];

int s[],h,t;

inline long long squa(long long a){    return a*a;    }

inline long long count(int x,int y){    return ((f[x]+squa(T[x]))-(f[y]+squa(T[y])))/(*(T[x]-T[y]));    }

int main(){

    int n=read(),l=read();

    for(int i=;i<=n;++i){

        c[i]=read()+c[i-];

        f[i]=1e18;

        T[i]=c[i]+i;

        M[i]=c[i]+i-l-;

    }

    for(int i=;i<=n;++i){

        while(h<t&&count(s[h],s[h+])<=M[i])    h++;

        int x=s[h];

        f[i]=f[x]+squa(M[i]-T[x]);

        while(h<t&&count(s[t-],s[t])>=count(s[t],i))    t--;

        s[++t]=i;

    }

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

    return ;

}