[文章目录]
Description
新的电话线架设在已有的N(2 <= N <= 100,000)根电话线杆上， 第i根电话线杆的高度为height_i米(1 <= height_i <= 100)。 电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端 如果这两根电话线杆的高度不同，那么FJ就必须为此支付 C*电话线杆高度差(1 <= C <= 100)的费用。当然，你不能移动电话线杆， 只能按原有的顺序在相邻杆间架设电话线。Farmer John认为 加高某些电话线杆能减少架设电话线的总花费，尽管这项工作也需要支出一定的费用。 更准确地，如果他把一根电话线杆加高X米的话，他得为此付出X^2的费用。 请你帮Farmer John计算一下，如果合理地进行这两种工作，他最少要在这个电话线改造工程上花多少钱。
先想朴素dp：由于到达每个hi对答案的作用取决于上一个的高度，所以dp[i][j]表示前i个，第i个高度为j的最小花费。得到方程：dp[i][j]=min(dp[i-1][k]+c*abs(j-k))+(j-hi)^2
然后优化，先去掉abs，分成两类，up[j],down[j]表示在高度以上或者以下的最小节点。发现，如果up[j]<up[j+1]+c，那么肯定以后向下接线的不需要j+1了，直接O(n)预处理出下一轮每个高度应当连接的高度。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,c,dp[2][110],h[101000],mx,ans=0x7f7f7f7f;
bool flag;
int up[110],down[110];
inline int Abs(int x){return x>0?x:-x;}
int main()
{
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++) scanf("%d",h+i),mx=max(h[i],mx);
for(int i=0;i<=mx;i++) up[i]=down[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=0;j<h[i];j++) dp[flag][j]=0x3f3f3f3f;
for(int j=h[i];j<=mx;j++)
dp[flag][j]=min(dp[flag^1][up[j]]+c*(up[j]-j),dp[flag^1][down[j]]+c*(j-down[j]))+(j-h[i])*(j-h[i]);
for(int j=0;j<=mx;j++)
{
if(j!=0&&dp[flag][down[j-1]]+c*(j-down[j-1])<dp[flag][j])
down[j]=down[j-1];
else down[j]=j;
}
for(int j=mx;j>=0;j--)
{
if(j!=mx&&dp[flag][up[j+1]]+c*(up[j+1]-j)<dp[flag][j])
up[j]=up[j+1];
else up[j]=j;
}
flag^=1;
}
flag^=1;
for(int i=h[n];i<=mx;i++) ans=min(ans,dp[flag][i]);
printf("%d\n",ans);
return 0;
}