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

#include<bits/stdc++.h>
using namespace std;
int n,c,h[100005],f[100005][105],ma;
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]),ma=max(ma,h[i]);
	memset(f,0x3f,sizeof(f));
	for(int i=h[1];i<=ma;i++)f[1][i]=(i-h[1])*(i-h[1]);
	for(int i=2;i<=n;i++){
		int tem=0x3fffffff;
		for(int j=h[i-1];j<=ma;j++){
			tem=min(tem,f[i-1][j]-c*j);
			if(j>=h[i])f[i][j]=tem+c*j;
		}tem=0x3fffffff;
		for(int j=ma;j>=h[i];j--){
			tem=min(tem,f[i-1][j]+c*j);
			f[i][j]=min(tem-c*j,f[i][j]);
			f[i][j]+=(j-h[i])*(j-h[i]);
		}
	}int mi=0x3fffffff;
	for(int i=h[n];i<=ma;i++)mi=min(mi,f[n][i]);
	cout<<mi;
	return 0;
}