记录编号	454150	评测结果	AAAAAAATTT
题目名称	[HZOI 2016]架设电话线路	最终得分	70
用户昵称	Regnig Etalsnart	是否通过	未通过
代码语言	C++	运行时间	3.407 s
提交时间	2017-09-28 14:05:31	内存使用	28.60 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;
}
int main(){;}
int syy=Main();