[bzoj 3156] 防御准备

Description

Input

第一行为一个整数N表示战线的总长度。

第二行N个整数,第i个整数表示在位置i放置守卫塔的花费Ai。

Output

共一个整数,表示最小的战线花费值。

Sample Input

10
2 3 1 5 4 5 6 3 1 2

Sample Output

18

HINT

1<=N<=10^6,1<=Ai<=10^9

Solution

一开始倒着做发现插入队列时必须要滞后,所以就GG了

其实强制第i个点建立站就好了= =和导弹拦截一个思路

f(i)表示逆序数组以后(为了方便处理),第i个点强制建塔的最小花费

f[i]=min\begin{Bmatrix}f[j]+\frac{(i-j)(i-j-1)}{2}+a[i]\end{Bmatrix}

至于中间那个怎么来的,推推贡献就好

然后xjb斜率优化就行

 

发表评论