「BZOJ1911」[Apio2010] 特别行动队commando

2014年5月18日4,9221

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]

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
LightningUZ Recent comment authors
  Subscribe  
提醒
LightningUZ

假装看风景可还行