记录编号	454281	评测结果	AAAAAAAAAT
题目名称	[HZOI 2016]架设电话线路	最终得分	90
用户昵称	皓芷	是否通过	未通过
代码语言	C++	运行时间	2.568 s
提交时间	2017-09-28 18:48:46	内存使用	39.22 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define mysister
using namespace std;
const int maxn=100001;
const int maxm=101;
void in(int &x)
{
	x=0;int f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	x*=f;
}
int n,c,cm[maxm],f[maxn][maxm],h[maxn],ans=0x7fffffff,hist=0,mi[maxm];
int main()
{
	freopen("phonewire.in","r",stdin);
	freopen("phonewire.out","w",stdout);
	in(n);in(c);
	for(int i=1;i<=100;i++)cm[i]=cm[i-1]+c;
	for(int i=1;i<=100;i++)mi[i]=i*i;
	for(int i=1;i<=n;i++)
	  {in(h[i]);hist=max(hist,h[i]);}
	memset(f,0x7f,sizeof(f));
	for(int i=0;i<=100;i++)f[0][i]=0;
	for(int i=1;i<=n;i++)
	  for(int j=h[i];j<=hist;j++)
	    for(int k=h[i-1];k<=hist;k++)
	  	  f[i][j]=min(f[i][j],f[i-1][k]+cm[(int)abs(j-k)]+mi[j-h[i]]);
	for(int i=h[n];i<=hist;i++)
	  ans=min(ans,f[n][i]);
	printf("%d",ans);
	return 0;
}