【斜率优化dp】玩具装箱

动态规划DP

传送门：BZOJ1010

思路：用$f_i$记录前i个物品的最小费用，dp即可，可以斜率优化。

注意：特判横坐标相同的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 300000
#define LL long long
LL n,L,a[N],pre[N],f[N],b[N],d[N],x[N],y[N],q[N];
double K(LL i,LL j){return (double)(1.0*y[i]-y[j])/(x[i]-x[j]);}
inline int getint(){
	char ch; LL sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
int main(){
	n=getint(); L=getint();
	for (int i=1;i<=n;i++){a[i]=getint(); pre[i]=pre[i-1]+a[i];}
	f[0]=0; b[0]=0; d[0]=b[0]+L+1; x[0]=2*d[0]; y[0]=f[0]+d[0]*d[0];
	int tt=1,ww=1; q[1]=0;
	for (int i=1;i<=n;i++){
		b[i]=i+pre[i]; d[i]=b[i]+L+1;
		while (tt<ww && K(q[tt],q[tt+1])<=b[i]) tt++;
		f[i]=b[i]*b[i]-x[q[tt]]*b[i]+y[q[tt]];
		x[i]=d[i]*2; y[i]=f[i]+d[i]*d[i];
		while (tt<ww && K(q[ww-1],q[ww])>K(q[ww],i)) ww--;
		q[++ww]=i;
	}
	
	printf("%lld\n",f[n]);
	
	return 0;
}