【题意】给定一排n根杆高度hi，一个常数C，杆升高x的代价为x^2，相邻两杆之间架设电话线代价为高度差*C，求总代价最小。
【算法】DP+辅助数组优化
【题解】令f[i][j]表示第i根杆高度为j的最小代价。
f[i][j]=min(f[i-1][k]+C*|j-k|+(a[i]-j)^2)。复杂度O(n*100*100)。
考虑优化方向是省略k这一维的枚举，故分离方程中和k无关的变量。
f[i][j]=min(f[i-1][k]-C*k)+C*j+(a[i]-j)^2，k<=j
f[i][j]=min(f[i-1][k]+C*k)-C*j+(a[i]-j)^2，k>j
这样就可以用辅助数组优化了。
b[i][j]=min(f[i][k]-C*k),k<=j
c[i][j]=min(f[i][k]+C*k),k>=j
则方程转化为：
f[i][j]=min( b[i-1][j] + C*j , c[i-1][j+1] - C*j )+C*j+(a[i]-j)^2。
复杂度O(n*100)。
细节：
1.必须初始化f[1]。
2.是c[j+1]，因为统计的时候是>=。
3.所有初始化为inf。
#include<cstdio>
int min(int a,int b){return a<b?a:b;}
const int maxn=,maxk=,inf=0x3f3f3f3f;
int f[maxk],b[maxk],c[maxk],n,m,C,a[maxn];
int main(){
scanf("%d%d",&n,&C);
for(int i=;i<=n;i++){scanf("%d",&a[i]);if(a[i]>m)m=a[i];}
b[]=c[m+]=inf;
for(int i=;i<=n;i++){
if(i==)for(int j=;j<=m;j++)if(j>=a[i])f[j]=(a[i]-j)*(a[i]-j);else f[j]=inf;
else for(int j=;j<=m;j++)if(j>=a[i])f[j]=min(b[j]+C*j,c[j+]-C*j)+(a[i]-j)*(a[i]-j);else f[j]=inf;
for(int j=;j<=m;j++)b[j]=min(b[j-],f[j]-C*j);
for(int j=m;j>=;j--)c[j]=min(c[j+],f[j]+C*j);
}
int ans=inf;
for(int i=;i<=m;i++)ans=min(ans,f[i]);
printf("%d",ans);
return ;
}