【bzoj1911】[Apio2010]特别行动队commando

2014年5月18日3,5090

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

题解

我发现似乎掌握了特殊的斜率优化技巧,我会假装四处看风景

dp方程:f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)

如果j>k且j比k更优

f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i]