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

#include<bits/stdc++.h>
using namespace std;
int a[100005],f[100005][105];
int main()
{
	freopen("phonewire.in","r",stdin);
	freopen("phonewire.out","w",stdout);
	int n,c;
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	memset(f,0x3f3f3f3f,sizeof(f));
	for (int i=0;i<=100;i++)
	f[1][i]=(a[1]-i)*(a[1]-i);
	for (int i=1;i<=n;i++)
	{
		int l=0x3f3f3f3f;
		for (int j=0;j<=100;j++)
		{
			if (j>=a[i-1]) l=min(l,f[i-1][j]-j*c);
			if (j>=a[i]) f[i][j]=min(f[i][j],l+(j-a[i])*(j-a[i])+j*c);
		}
		l=0x3f3f3f3f;
		for (int j=100;j>=0;j--)
		{
			if (j>=a[i-1]) l=min(l,f[i-1][j]+j*c);
			if (j>=a[i]) f[i][j]=min(f[i][j],l+(j-a[i])*(j-a[i])-j*c);
		}
	}
	int minn=100000000;
	for (int i=0;i<=100;i++)
	minn=min(minn,f[n][i]);
	printf("%d",minn);
	return 0;
}