【DP+斜率优化】[HNOI2008][HYSBZ/BZOJ1010]玩具装箱toy

时间:2021-10-19 00:51:14

题目链接

分析

我们很容易想到DP,并且得到状态转移方程式( f 为费用, sum 为C数组的前缀和)

fi=min(fj+sumisumj+ij1L)2

直接做肯定超时,考虑优化。
令j,k为i之前任意两个决策点,j < k,k更优
(fk+sumisumk+ik1L)2(fj+sumisumj+ij1L)2


fk+(sumkk)2+2(sumkk)(sumi+i1l)+(sumi+i1l)2fj+(sumjj)2+2(sumjj)(sumi+i1l)+(sumi+i1l)2

fk+(sumk+k)22(sumk+k)(sumi+i1l)fj+(sumj+j)22(sumj+j)(sumi+i1l)

fkfj+(sumk+k)2(sumj+j)22(sumk+ksumjj)(sumi+i1l)

fkfj+(sumk+k)2(sumj+j)22(sumk+ksumjj)sumi+i1l

根据斜率,维护递增的单调序列(即下凸包),即可求解。

代码

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 50000
#define S(i) sum[i]+i-1-l
int a[MAXN+10],n,l,q[MAXN+10],fr,bk;
long long sum[MAXN+10],f[MAXN+10];
void Read(int &x){
    char c;
    while(c=getchar(),c!=EOF)
        if(c>='0'&&c<='9'){
            x=c-'0';
            while(c=getchar(),c>='0'&&c<='9')
                x=x*10+c-'0';
            ungetc(c,stdin);
            return;
        }
}
void read(){
    Read(n),Read(l);
    for(int i=1;i<=n;i++)
        Read(a[i]),sum[i]=sum[i-1]+a[i];
}
//j<k
//f[i]=f[j]+(sum[i]-sum[j]+i-j-1-l)^2
//f[j]+(sum[i]-sum[j]+i-j-1-l)^2>=f[k]+(sum[i]-sum[k]+i-k+1-l)^2
//f[j]+(-sum[j]-j)^2+2*(-sum[j]-j)*(sum[i]+i-1-l)+(sum[i]+i-1-l)^2>=f[k]+(-sum[k]-k)^2+2*(-sum[k]-k)*(sum[i]+i-1-l)+(sum[i]+i-1-l)^2
//f[j]+(sum[j]+j)^2-2*(sum[j]+j)*(sum[i]+i-1-l)>=f[k]+(sum[k]+k)^2-2*(sum[k]+k)*(sum[i]+i-1-l)
//(f[j]+(sum[j]+j)^2-(f[k]+sum[k]+k)^2)>=2*(sum[i]+i-1-l)
//((f[j]+(sum[j]+j)^2-(f[k]+(sum[k]+k)^2))/(2*(sum[j]+j-sum[k]-k))<=(sum[i]+i-1-l)
inline double Get_slope(int j,int k){
    return 1.0*(f[j]-f[k]+(sum[j]+j)*(sum[j]+j)-(sum[k]+k)*(sum[k]+k))/(2*(sum[j]+j-sum[k]-k));
}
void dp(){
    int i;
    q[0]=fr=bk=0;
    for(i=1;i<=n;i++){
        while(fr<bk&&Get_slope(q[fr],q[fr+1])<=S(i))
            fr++;
        f[i]=f[q[fr]]+(sum[i]-sum[q[fr]]+i-q[fr]-1-l)*(sum[i]-sum[q[fr]]+i-q[fr]-1-l);
        while(fr<bk&&Get_slope(q[bk-1],q[bk])>=Get_slope(q[bk],i))
            bk--;
        q[++bk]=i;
    }
}
int main()
{
    read();
    dp();
    printf("%lld",f[n]);
}