[bzoj 1911][Apio2010]特别行动队

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

Solution

f(i)表示把前i个士兵分配好的最大战斗力

f[i]=max.\begin{Bmatrix}f[j]+a\times(s[i]-s[j])^{2}+b\times(s[i]-s[j])+c\end{Bmatrix}

xjb斜率优化搞搞就好

 

发表评论