记录编号	315216	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]架设电话线路	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.492 s
提交时间	2016-10-04 21:40:24	内存使用	43.02 MiB

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 100010;
int F[maxn][111] = {0};
int N,C,h[maxn] = {0},Min = 0x7f7f7f7f;
int ABS(int x,int y)
{
	int q = abs(x-y);
	return C*q;	
}
int M()
{
	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]);
	memset(F,0x3f,sizeof(F));
	for(int i = 0;i<=100;i++)F[1][i] = (i-h[1])*(i-h[1]);
	for(int i = 2;i<=N;i++)
	{
		int q1 = 0x7f7f7f7f;
		for(int j = 0;j<=100;j++)
		{
			if(j>=h[i-1])q1 = min(q1,F[i-1][j]-C*j);
			if(j>=h[i])F[i][j] = min(q1+(j-h[i])*(j-h[i])+C*j,F[i][j]);
		}
		int q2 = 0x7f7f7f7f;
		for(int j = 100;j>=0;j--)
		{
			if(j>=h[i-1])q2 = min(q2,F[i-1][j]+C*j);
			if(j>=h[i])F[i][j] = min(F[i][j],q2-C*j+(j-h[i])*(j-h[i]));
		}
	}
	for(int i = h[N];i<=100;i++)Min = min(Min,F[N][i]);
	printf("%d",Min);
}
int po = M();
int main(){;}