「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之后跑的更慢了,玄学



6+
文章已创建 93

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部