【bzoj3156】防御准备

2014年6月16日1,9640

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

题解

裸的斜率优化

把a[i]都反过来

sum[i]=sum[i-1]+i

f[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*j}