lp3195 HNOI2008 玩具装箱TOY

一道斜率优化的经典例题。
对于这道题，DP式是容易得到的：
$$f_i=min\{f_j+(\sum_{j+1}^ia_{i}+i-j-1-L)^2\}$$
前缀和优化：
$$f_i=min\{f_j+(sm_i-sm_j+i-j-1-L)^2\}$$
考虑到这是一个与取值平方相关的式子，尝试用斜率优化来化简。
令：
$$u_i=sm_i+i$$
$$f_i=min{f_j+(u_i-u_j-1-L)^2}$$
对于右式，我们假定\(1\le j<k<i\)且从\(k\)转移较优。
那么我们有：
$$f_{k}+(u_{i}-u_{k}-1-L)^2\le f_{j}+(u_{i}-u_{j}-1-L)^2$$
展开并移项化简：
$$2u_{i}(u_{j}-u_{k})\le f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2$$
令：
$$g_{i}=(u_{i}+1+L)^2$$
并不妨假定：
$$u_{j}!=u_{k}$$
可得：
$$2u_{i}\le\frac{f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2}{(u_{j}-u_{k})}$$
故而，若要使得答案更大，则上式必然成立。
考虑到这个式子符合单调队列的性质，我们可以上一个类似单调队列的数据结构来维护右侧的式子，也就是俗称的“斜率”。
这就完成了斜率优化。

#include<iostream>
#include<cstdio>
#include<queue>


int n,L;
double sm[50005],f[50005];
int q[50005],l,r;
inline double u(int X){
	return sm[X]+X;
}
inline double g(int X){
	return u(X)+L+1;
}
inline double x(int X){
	return g(X);
}
inline double y(int X){
	return f[X]+g(X)*g(X);
}
inline double k(int A,int B){
	return (y(A)-y(B))/(x(A)-x(B));
}

void init(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;++i){
		scanf("%lf",&sm[i]);
		sm[i]+=sm[i-1];
	}
	l=r=1;
	for(int i=1;i<=n;++i){
		while(l<r&&k(q[l],q[l+1])<2*u(i)){
			++l; 
		} 
		f[i]=f[q[l]]+(u(i)-g(q[l]))*((u(i)-g(q[l])));
		while(l<r&&k(i,q[r-1])<k(q[r-1],q[r])){
			--r;
		}
		q[++r]=i;
	}
	printf("%lld\n",(long long)f[n]);
}

int main(){
	init();
	return 0;
}