【HNOI2008】玩具装箱_综合

题面

?? $n≤5*10^4,0≤L，C_i≤10^7$

解法

??我们可以得出一个 $n^2$ 的DP：设 $f[i]$ 表示决策完第 $i$ 件玩具的最小花费， $s[i]=\sum_{k=1}^i C_i$ ，那么有： $f[i]=min$ { $f[j]+(s[i]-s[j]+i-j-1-l)^2$ }
??将里面的式子展开可以得到： $f[j]+(s[i]+i)^2+(s[j]+j)^2+(l+1)^2-2*(s[i]+i)*(s[j]+j)-2*(s[i]+i)*(l+1)+2*(s[j]+j]*(l+1)$
??其中， $(s[i]+i)^2$ ， $(l+1)^2$ ， $-2*(s[i]+i)*(l+1)$ 属于和 $j$ 无关的量，直接拉出来，剩下的部分为： $f[j]+(s[j]+j)^2-2*(s[j]+j)*(s[i]+i-l-1)$
??假设 $i$ 可以从 $j$ 以及 $k$ 转移得来，并且从 $k$ 转移更优，那么有：

$f [j] + (s [j] + j) 2 ? 2 ? (s [j] + j) ? (s [i] + i ? l ? 1) < f [k] + (s [k] + k) 2 ? 2 ? (s [k] + k) ? (s [i] + i ? l ? 1)$ $f[j]+(s[j]+j)^2-2*(s[j]+j)*(s[i]+i-l-1)<f[k]+(s[k]+k)^2-2*(s[k]+k)*(s[i]+i-l-1)$
$f [ j ] + ( s [ j ] + j ) 2 ? f [ k ] ? ( s [ k ] + k ) 2 2 ? [ ( s [ j ] + j ) ? ( s [ k ] + k ) ] < s [i] + i ? l ? 1 \cdot \cdot \cdot \cdot \cdot \cdot ①$ $\dfrac{f[j]+(s[j]+j)^2-f[k]-(s[k]+k)^2}{2*[(s[j]+j)-(s[k]+k)]}<s[i]+i-l-1 ······①$
??接下来就只需要根据式①进行斜率优化的过程就可以了

复杂度

O（ $nlogn$ ）

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Rint register int
#define Lint long long int
using namespace std;
const int N=50010;
Lint s[N],f[N];
int q[N],c[N],n,L,head,tail;;
Lint getup(int i,int j)
{return f[i]+(s[i]+i)*(s[i]+i)-f[j]-(s[j]+j)*(s[j]+j);
}
Lint getdown(int i,int j)
{return 2*(s[i]+i-s[j]-j);
}
bool judge(int i,int j,int C)
{Lint A=getup( i,j ),B=getdown( i,j );return A<=B*C;
}
bool Judge(int i,int j,int k)
{return getup( i,j )*getdown( j,k )<=getup( j,k )*getdown( i,j );
}
Lint cal(int i,int j)
{return f[j]+(s[i]-s[j]+i-j-1-L)*(s[i]-s[j]+i-j-1-L);
}
int main()
{scanf("%d%d",&n,&L);for(int i=1;i<=n;i++){scanf("%d",&c[i]);s[i]=s[i-1]+c[i];}head=tail=q[0]=0;for(int i=1;i<=n;i++){while( head+1<=tail && judge( q[head+1],q[head],s[i]+i-L-1 ) )   ++head;f[i]=cal( i,q[head] );while( head+1<=tail && Judge( i,q[tail],q[tail-1] ) )   tail--;q[++tail]=i;}printf("%lld\n",f[n]);return 0;
}