# Bzoj1705 telephone wire 架设电话线

Posted by yjjr's blog on February 6, 2018

Description

Input

* 第1行: 2个用空格隔开的整数：N和C

* 第2..N+1行: 第i+1行仅有一个整数：height_i

Output

* 第1行: 输出Farmer John完成电话线改造工程所需要的最小花费

Sample Input

5 2
2
3
5
1
4

H[i][j]=min{abs(k-j)+h[i-1][k]}+(j-wi)^2

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
const int inf=0x3f3f3f,maxh=106,maxn=3e5+6;
int f[306],g[306],n,c,a[maxn],headsum[maxn],tailsum[maxn],ans=inf;

int main()
{
scanf("%d%d",&n,&c);
rep(i,1,n)scanf("%d",&a[i]);
mem(f,inf);
rep(i,a[1],maxh)f[i]=(i-a[1])*(i-a[1]);
rep(i,2,n){
memcpy(g,f,sizeof f);
rep(j,0,maxh)f[j]=headsum[j]=tailsum[j]=inf;
headsum[0]=g[0];
rep(j,1,maxh)headsum[j]=min(headsum[j-1],g[j]-c*j);
tailsum[maxh]=g[maxh]+maxh*c;
dep(j,maxh-1,0)tailsum[j]=min(tailsum[j+1],g[j]+c*j);
rep(j,a[i],maxh)f[j]=min(tailsum[j]-c*j,headsum[j]+c*j)+(j-a[i])*(j-a[i]);
}
rep(i,a[n],maxh)ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}