洛谷P3195 [HNOI2008]玩具装箱

题目链接:https://www.luogu.com.cn/problem/P3195

 

对于这道题，可以用斜率优化的方法，

转移方程

dp[i]=min(dp[j]+(i-j-L-1+sun[i]-sum[j])^2),i>j;

可以转化为

 (2(sun[i]+i)(sum[j]+j+L)+(dp[i]-(sum[i]+i)^2)=(dp[j]+((sum[j]+j)+L)^2)

y=(dp[j]+((sum[j]+j)+L)^2)

k=2(sun[i]+i)

x=(sum[j]+j+L)

b=(dp[i]-(sum[i]+i)^2)

这样维护一个凸包，就能解决问题

时间复杂度o(n)

代码:

#include<stdio.h>
#define N 500001
#define ll long long
int n,t=0;
ll L,h=1,Q[N],S[N],dp[N];
ll minn(ll a,ll b){return a<b?a:b;}
ll X(ll j){return S[j];}
ll Y(ll j){return dp[j]+(S[j]+L)*(S[j]+L);}
long double slope(ll i,ll j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
    scanf("%d%lld",&n,&L);++L;
    for(int i=1;i<=n;S[i]+=S[i-1]+1,i++)scanf("%lld",S+i);
    Q[++t]=0;
    int j;
    for(int i=1;i<=n;i++){
        while(h<t&&slope(Q[h],Q[h+1])<=2*S[i])++h;
        dp[i]=dp[j=Q[h]]+(S[i]-S[j]-L)*(S[i]-S[j]-L);
        while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
    return 0;
}