P3195 [HNOI2008]玩具装箱TOY

题意：有1-n个玩具需要打包每个玩具的有其长度可以一段区间一段区间地打包问打包完所有地玩具需要的最小代价

打包一段区间的代价为玩具个数-1 加上所有玩具的长度减L 的平方（L为给定值)

dp的转移式很好得到：$dp[i]=min(dp[j]+(sum[i]+i−sum[j]−j−L−1) ^2 ) (j<i)$

设 $a[k] = sum[k] + k$

$ b[k] = sum[k] + k + 1 + L$

带入原式： $ dp[i]=dp[j]+a[i]^2-2a[i]*b[j]+b[j]^2$

　　　　$dp[j]+b[j]^2 ( y ) =2a[i]b[j] (kx) + dp[i]-a[i]^2 (b)$

很明显斜率为2a[i] 显然为递增的所以只要维护一个递增的斜率即可第一个斜率$(j,j+1)>2a[i] $即为答案

同时队列右端要维护最小值因为是一个凸包

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
/////////////////////////////////////
const int N=1e5+10;
ll L,n,m,sum[N],dp[N];
ll a(int x){return sum[x]+x;}
ll b(int x){return sum[x]+x+1+L;}
ll X(int x){return b(x);}
ll Y(int x){return dp[x]+b(x)*b(x);}
double sp(int a,int b){return (Y(a)-Y(b))/(X(a)-X(b));}
int q[N],l,r;
int main()
{
    cin>>n>>L;
    rep(i,1,n)scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
    l=r=1;
    rep(i,1,n)
    {
        while(l<r && sp(q[l],q[l+1])<2*a(i))l++;
        dp[i]=dp[q[l]]+(a(i)-b(q[l]))*(a(i)-b(q[l]));
        while(l<r && sp(q[r-1],q[r])>sp(q[r],i))r--;
        q[++r]=i;
    }
    cout<<dp[n];
    return 0;
}

View Code