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

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=100010,maxh=110;
int h[maxn],c,f[maxn][maxh],n;

void beg(){
    freopen("phonewire.in","r",stdin);
    freopen("phonewire.out","w",stdout);
}

int calval(int x){
    return x*x;
}

int main(){
    beg();
    scanf("%d%d",&n,&c);
    for (int i=1;i<=n;i++){
	scanf("%d",&h[i]);
    }
    memset(f,0xff/3,sizeof(f));
    for (int i=0;i<=100;i++) f[1][i]=calval(h[1]-i);
    for (int i=2;i<=n;i++){
	int temp=1e9;
	for (int j=0;j<=100;j++){
	    if (j>=h[i-1]) temp=min(temp,f[i-1][j]-j*c);
	    if (j>=h[i]) f[i][j]=min(f[i][j],temp+calval(j-h[i])+j*c);
	}
	temp=1e9;
	for (int j=100;j>=0;j--){
	    if (j>=h[i-1]) temp=min(temp,f[i-1][j]+j*c);
	    if (j>=h[i]) f[i][j]=min(f[i][j],temp+calval(j-h[i])-j*c);
	}
    }
    int t=1e9;
    for (int i=h[n];i<=100;i++){
	t=min(t,f[n][i]);
    }
    printf("%d\n",t);
}