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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int INF=0x7fffffff;
int f[100001][101];
int h[100001];
int n,c,H=-INF,ans=INF;

int main(){
	freopen("phonewire.in","r",stdin);
	freopen("phonewire.out","w",stdout);
	scanf("%d%d",&n,&c);

	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
		H=max(H,h[i]);
	}
	
	for(int i=h[1];i<=H;i++)
	f[1][i]=(i-h[1])*(i-h[1]);
	
	for(int i=2;i<=n;i++)
	for(int j=h[i];j<=H;j++){
		f[i][j]=INF;
		for(int k=h[i-1];k<=H;k++)
		if(f[i][j]>f[i-1][k]+(int)abs(c*(k-j))+(j-h[i])*(j-h[i]))
			f[i][j]=f[i-1][k]+(int)abs(c*(k-j))+(j-h[i])*(j-h[i]);
		else break;
	}

	for(int i=h[n];i<=H;i++)
	ans=min(ans,f[n][i]);
	
	printf("%d",ans);
	return 0;
}