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

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 2147483647
using namespace std;
const int maxn=100001;
int n,c,h[maxn],f[maxn][101],maxx,ans=INF,i,j,k;
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;
}