记录编号	454523	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]架设电话线路	最终得分	100
用户昵称	玉带林中挂	是否通过	通过
代码语言	C++	运行时间	1.495 s
提交时间	2017-09-29 08:00:44	内存使用	39.22 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define INF 1<<30
using namespace std;
const int maxn=100001;
int n,c,h[maxn],f[maxn][101],maxx,ans=INF,i,j,k;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
} 
int min(int a,int b)
{
	return a<b?a:b;
}
int max(int a,int b)
{	
	return a>b?a:b;
}
int abs(int x)
{
	return x>=0?x:-x;
}
int main()
{
	freopen("phonewire.in","r",stdin);freopen("phonewire.out","w",stdout);
	n=read();c=read();
	for(i=1;i<=n;i++)
	{
		h[i]=read();
		maxx=max(maxx,h[i]);
	}
	for(i=h[1];i<=maxx;i++)f[1][i]=(i-h[1])*(i-h[1]);
	for(i=2;i<=n;i++)
	{
		for(j=h[i];j<=maxx;j++)f[i][j]=INF;
		for(j=h[i-1];j<=maxx;j++)for(k=h[i];k<=maxx;k++)
			f[i][k]=min(f[i][k],f[i-1][j]+(k-h[i])*(k-h[i])+c*abs(j-k));
	}
	for(i=h[n];i<=maxx;i++)ans=min(ans,f[n][i]);
	printf("%d\n",ans);
	return 0;
}