【bzoj1911】[Apio2010]特别行动队 斜率优化dp
优化 DP 特别 斜率
2023-09-11 14:22:40 时间
题目描述
输入
输出
样例输入
4
-1 10 -20
2 2 3 4
样例输出
9
题解
斜率优化dp
设f[i]表示前i个士兵的战斗力之和的最大值。
那么有f[i]=f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c,
其中sum为前缀和。
展开平方,整理得f[j]+a*sum[j]^2-b*sum[j]=2*a*sum[i]*sum[j]+f[i]-a*sum[i]^2-b*sum[i]-c。
这样就得到了y=kx+b的形式,而且要求的是其中b的最大值。
于是维护一个上凸包即可,与下凸包的差别就在于斜率比较时'>'和'<'的不同。
#include <cstdio> #define y(i) (f[i] + a * sum[i] * sum[i] - b * sum[i]) #define x(i) sum[i] long long sum[1000010] , f[1000010]; int q[1000010] , l , r; int main() { int n , i; long long a , b , c , x; scanf("%d%lld%lld%lld" , &n , &a , &b , &c); for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &x) , sum[i] = sum[i - 1] + x; for(i = 1 ; i <= n ; i ++ ) { while(l < r && y(q[l + 1]) - y(q[l]) > (x(q[l + 1]) - x(q[l])) * 2 * a * sum[i]) l ++ ; f[i] = f[q[l]] + a * (sum[i] - sum[q[l]]) * (sum[i] - sum[q[l]]) + b * (sum[i] - sum[q[l]]) + c; while(l < r && (y(i) - y(q[r])) * (x(q[r]) - x(q[r - 1])) > (x(i) - x(q[r])) * (y(q[r]) - y(q[r - 1]))) r -- ; q[++r] = i; } printf("%lld\n" , f[n]); return 0; }
相关文章
- hdu1505 暴力或dp优化
- 如何大幅优化NGUI的堆内存分配
- 蒟蒻关于斜率优化DP简单的总结
- keil mdk编译器学习笔记(5)——如何确保某一段程序不被优化掉 使用keil判断ARM的冷启动和热启动的方法
- 基于NSGAII的多目标优化算法的MATLAB仿真
- 【C++】返回值优化(RVO)
- 详解DBLINK操作的语句执行机制及优化方式
- 记一次区域DB突发变慢的SQL优化博弈
- 自己动手构造编译系统:编译、汇编与链接2.1.6 编译优化
- oracle sql语句优化(转载)
- POJ 1160 Post Office (四边形不等式优化DP)
- 小程序优化(1)
- UITableView优化那点事
- NOT IN、NOT EXISTS的相关子查询改用LEFT JOIN--sql2000性能优化
- 学习笔记:Twitter核心数据类库团队的Hadoop优化经验
- [js高手之路]性能优化技巧 - 缓存与函数重载实战
- 浅谈线段树优化DP
- Android绘制优化(一)绘制性能分析
- 优化报表系统结构之报表server计算
- hdu 5411 CRB and Puzzle (矩阵高速幂优化dp)
- 数据中心优化专家Future Facilities公司推出6Sigma DCX最新版本
- 【bzoj3672】[Noi2014]购票 斜率优化dp+CDQ分治+树的点分治
- 【bzoj3675】[Apio2014]序列分割 斜率优化dp