记录编号	315193	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]架设电话线路	最终得分	100
用户昵称	gls1196	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2016-10-04 21:12:21	内存使用	0.31 MiB

//不用单调队列，开个变量记录最小值即可。 
#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,la=0,no=1,mi;
	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;
		mi=f[la][0];
		for(int j=0;j<=maxn;j++){
			mi=min(f[la][j]-j*m,mi);
			if(j>=hi)f[no][j]=mi+j*m+(hi-j)*(hi-j);
		}
		mi=f[la][maxn]+maxn*m;
		for(int j=maxn;j>=0;j--){
			mi=min(f[la][j]+j*m,mi);
			if(j>=hi)f[no][j]=min(f[no][j],mi-j*m+(hi-j)*(hi-j));
		}
	}
	int ans=inf;
	for(int i=hi;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;
}