「BZOJ1911」[Apio2010] 特别行动队 – 斜率优化

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]\)

所以拿一个单调队列维护斜率

话说BZOJ的老爷机老爷一点也就算了,还tm这么不稳定,我开了O2之后跑的更慢了,玄学 继续阅读 「BZOJ1911」[Apio2010] 特别行动队 – 斜率优化

5+