记录编号	286431	评测结果	AAAAAAAAAA
题目名称	2240.[HZOI 2016]架设电话线路	最终得分	100
用户昵称	gls1196	是否通过	通过
代码语言	C++	运行时间	0.157 s
提交时间	2016-07-30 22:15:21	内存使用	0.28 MiB

/*
dp[i][j]=min(dp[i-1][k] + C*abs(j-k) + X)
当第 i 个儿子的身高j从第 i-1 个儿子的身高k转移时，( k<=j ) 
dp[i][j]=min(dp[i-1][k] + j*C-k*C + X);   
当第 i 个儿子的身高j从第 i-1 个儿子的身高k转移时，( k>=j )
dp[i][j]=min(dp[i-1][k] - j*C+k*C + X); 
  
对第一个个方程，我们令 g[i-1][k]=dp[i-1][k]-k*C,   
于是 dp[i][j] = min (f[i-1][k])+ j*C + X 。
我们就可以用单调队列进行优化了。
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef double db;
typedef long long ll;
const int inf=0x7f7f7f7f/2;
const int maxn=100;
int f[2][maxn+10];
int q[maxn+10];
int n,m;
void Qread(int &x){
	x=0;
	char ch;int zf=1;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if(ch=='-')zf=-1;
	else x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=10*x+ch-48;
	x=x*zf;
}
int DP(){
	scanf("%d%d",&n,&m);
	int hi,he,te,la=0,no=1;
	Qread(hi);
	for(int j=0;j<hi;j++)f[no][j]=inf;
		for(int j=hi;j<=maxn;j++)f[no][j]=(j-hi)*(j-hi);
	for(int i=1;i<n;i++){
		Qread(hi);
		la^=1,no^=1;
		for(int j=0;j<hi;j++)f[no][j]=inf;
	//	for(int j=hi;j<=maxn;j++)f[no][j]=(j-hi)*(j-hi);
		he=0,te=-1;
		for(int j=0;j<=maxn;j++){
			int tmp=f[la][j]-j*m;
			while(he<=te&&q[te]>=tmp)te--;
			q[++te]=tmp;
			if(j>=hi)f[no][j]=q[he]+j*m+(hi-j)*(hi-j);
		}
		he=0,te=-1;
		for(int j=maxn;j>=0;j--){
			int tmp=f[la][j]+j*m;if(j>=hi)
			while(he<=te&&q[te]>=tmp)te--;
			q[++te]=tmp;
			f[no][j]=min(f[no][j],q[he]-j*m+(hi-j)*(hi-j));
		}
	}
	int ans=inf;
	for(int i=0;i<=maxn;i++)
		ans=min(ans,f[no][i]);
	return ans;
}
int main(){
	freopen("phonewire.in","r",stdin);
	freopen("phonewire.out","w",stdout);
	printf("%d",DP());
	return 0;
}