最简单的转移楼下讲得很清楚了
$f[i][j]$ 表示前i棵电线杆,当第i根电线杆高度为j的时候费用,然后转移很方便,然后正常的TLE
不难发现,每次转移是个开口向上的二次函数(可以自己算算),然后我们枚举上一棵树的高度的过程中,
如果随着高度的增加费用增加了,就可以不用继续转移了
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,c,p,x,s,mh;
int h[100100];
int f[100100][100];
int main()
{
n=read();c=read();
for (register int i=1;i<=n;i++)
{
h[i]=read();
if (h[i]>mh) mh=h[i];
}
memset(f,1,sizeof(f));
for (register int i=h[1];i<=100;i++) f[1][i]=(i-h[1])*(i-h[1]);
for (register int i=2;i<=n;i++)
{
for (register int j=h[i];j<=mh;j++)//hm:电线杆的最大高度
{
s=(j-h[i])*(j-h[i]);//先算出来快些?
p=233333333;
for (register int k=h[i-1];k<=mh;k++)
{
x=f[i-1][k]+s+c*abs(k-j);
//下面和这一句是等效的,似乎快点?f[i][j]=min(f[i][j],x);
if (x<f[i][j])
{
f[i][j]=x;
}
if (x>p) break;//比上一个更多就不用转移了
p=x;
}
}
}
int ans=f[n][h[n]];
for (register int i=h[n]+1;i<=100;i++) ans=min(ans,f[n][i]);//找答案
printf("%d",ans);
return 0;
}
```