【bzoj2364】城市美化

2014年9月13日1,8913

Description

城市A需要美化市容市貌,现在有n个楼房排成一列,每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建,使楼房高度得到上升(不能让楼房高度下降),对一栋楼房修建,使其高度上升x,需要x2的费用。
当所有修建完成后,我们把相邻两楼高度的绝对值乘以c(0<=c<=1000),得到的就是城市损失的钱,我们把它同样看作是费用。现在想请你合理安排修建楼房的方案,使得所需费用最小。

Input

第一行两个数n和c。
接下来n行,每行一个数,表示每栋楼的高度。

Output

仅一行一个数,表示最小所需的费用。

Sample Input

5 5
2
2
1
6
8

Sample Output

31

HINT

数据范围
对于100%的数据,1<=n<=50000

题解

这道题原题数据范围是100w。。。

用f[i]表示前i个,且最后一段与i-1相同的最小代价

可以得到一些性质。。

仅当一个楼房两边都比它高,或者一个楼房处于边界,那么将它向上调整才有可能使代价减小

如果一个楼房两边都高于它,且最后它向上调整了,则两侧的楼房高度都应与它相同,直到有比它更高的为止

那么只要维护一个单调递减,每个为止x仅能从x-上一个比x高的楼房y之间转移

f[x]=min { f[i]+cal(i,x)}

而cal(i,x)这是个二次函数求极值问题。。。

 

  • Orzhzw2015年10月20日 下午7:11 回复

    能不能解释一下求极值这个函数、、

    #1  
    • hzwer2015年10月21日 下午10:42 回复

      额二次函数对称轴。。。

      #11
      • Orzhzw2015年10月22日 上午7:23 回复

        谢谢。。。我已经知道了。。。Orz学长

        #12