[bzoj 1911][Apio 2010]特别行动队（斜率优化DP）
2020-12-13 05:46
阅读：445
标签：http io line php dp ef 优化 c 题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1911 分析： 首先可以的到裸的方程f[i]=max{f[j]+a*(Si-Sj)^2+b*(Si-Sj)+c} 0 简化一下方程，我们知道对于一次项，最后结果肯定是b*Sn 所以可以写成f[i]=max{f[j]+a*(Si-Sj)^2+c} 0 我们不妨设0 即f[x]+a*(Si-Sx)^2+c>f[y]+a*(Si-Sy)^2+c 整理一下：(f[x]+a*Sx^2)-(f[y]+a*Sy^2)>2aSi*(Sx-Sy） 设g[x]=f[x]+a*x^2 那么原式可以化简成： g[Sx]-g[Sy] ------------- > 2aSi (右边是个常数哟） Sx - Sy 左边明显就是斜率的定义式，反过来也就是说如果存在0 所以可以维护一个斜率单调递减的单调队列就行了，每次的最优点就是单调队列的头 GG [bzoj 1911][Apio 2010]特别行动队（斜率优化DP）,搜素材,soscw.com [bzoj 1911][Apio 2010]特别行动队（斜率优化DP） 标签：http io line php dp ef 优化 c 原文地址：http://www.cnblogs.com/wmrv587/p/3883724.html
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[bzoj 1911][Apio 2010]特别行动队（斜率优化DP）
文章链接：http://soscw.com/essay/31738.html
文章标题：[bzoj 1911][Apio 2010]特别行动队（斜率优化DP）
文章链接：http://soscw.com/essay/31738.html
评论
亲，登录后才可以留言！