[HNOI2008]玩具装箱

Statement

Luogu

Solution

首先考虑最为暴力的做法,也就是我们直接设$f_i$表示将前$i$个玩具合并,那么有转移:
$$
f_i=\min_{j=1}^{i-1}{f_j+val(j+1,i)}
$$
这个时候很明显$val(j+1,i)=(x-L)^{2={[(i-(j+1)+\sum_{k=j+1}}ic_k]-L)}^2$

这个时候不妨设$s_i=\sum_{j=1}^{ic_j,a_i=i+s_i$,此时这个$val(j+1,i)=(a[i]-a[j]-1-L)}2$

注意到这个可以拆成$b=y-kx$的形式,那么就可以用维护一个下凸包然后每次取最前面的点即可.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define re register
#define ll long long
#define int ll
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef pair<int,int> pii;
inline int gi(){
    int f=1,sum=0;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
const int N=50010;
int c[N],n,L,s[N],f[N],q[N],a[N];
int calc(int i,int j){return f[j]+sqr(a[i]-a[j]-L);}
double slope(int i,int j){
    int y=a[j]*a[j]+2*a[j]*L+f[j],x=a[j];
    int Y=a[i]*a[i]+2*a[i]*L+f[i],X=a[i];
    return 1.*(Y-y)/(X-x);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    n=gi();L=gi()+1;int h=1,t=1;f[0]=0;q[1]=0;
    for(int i=1;i<=n;i++)c[i]=gi(),s[i]=s[i-1]+c[i],a[i]=s[i]+i;
    for(int i=1;i<=n;i++){
        while(h<t&&calc(i,q[h])>calc(i,q[h+1]))h++;
        f[i]=calc(i,q[h]);
        while(h<t&&slope(q[t-1],i)<=slope(q[t-1],q[t]))t--;
        q[++t]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}