记录编号	454147	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]架设电话线路	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	1.479 s
提交时间	2017-09-28 14:02:49	内存使用	39.20 MiB

#include<cstdio>
#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;
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);
	scanf("%d%d",&n,&c);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
		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;
}