决策单调性优化dp 专题练习
2024-08-24 16:18:18
决策单调性优化dp 专题练习
优化方法总结
一、斜率优化
对于形如 \(dp[i]=dp[j]+(i-j)*(i-j)\)类型的转移方程，维护一个上凸包或者下凸包，找到切点快速求解
技法：
1.单调队列 ： 在保证插入和查询的x坐标均具有单调性时可以使用
2.单调栈+二分：保证插入有单调性，不保证查询有单调性
3.分治+ 1 或 2：在每次分治时将\([l,mid]\)这段区间排序后插入，然后更新右区间\([mid+1,r]\)的答案
二.分治、单调队列维护有单调性的转移 （甚至还有分治套分治）
分治法介绍：
定义函数\(Solve(l1,r1,l2,r2)\)记录当前分治到被转移的区间是\(l1,r1\)，用来更新的区间是\([l2,r2]\)
枚举找到\(mid\)的决策点，根据单调性将\([l2,r2]\)分成两段，递归进行
复杂度上，每一个递归层的\([l1,r1]\)，\([l2,r2]\)都分别构成近似一整段[1,n]的区间，最多只有\(log n\)层，所以复杂度是\(nlogn\)
三.四边形不等式优化
练习
一、斜率优化
另一篇总结
Extra A：柠檬 题解传送门
Extra B ：牛学校 题解传送门
二、单调性优化
A: Lawrence 题解传送门
B: Lightning Conductor 题解传送门
C: 记忆的轮廓 题解传送门
D:区间 题解传送门
E:Post加强版 题解以及拓展
三、四边形不等式
石子合并。。。
最新文章
- bzoj 2753: [SCOI2012] 滑雪与时间胶囊 Label:MST
- christian louboutin ballerinas outlet
- 第三章 Git使用入门
- 【mongo】mongo数据转json时特殊类型处理
- Qlikview 图标控件实现动态分组
- Ajax中的XMLHttpRequest对象详解
- .net操作xml文件(新增.修改,删除,读取)---datagridview与xml文件
- UVA 714 Copying Books 二分
- QT5控件-QPushButton和QFocusFrame（按钮和焦点框）
- oracle 查询前一小时、一天、一个月、一年的数据
- linux使用FIO测试磁盘的iops
- Arcgis for Js之Graphiclayer扩展具体解释
- 三.redis 排序
- 安装IPython攻略
- Erlang的常驻模块与功能模块
- Python入门：购物车实例
- emwin之在中断服务程序中创建窗口的结果
- git 命令添加整个文件夹以及文件夹下的内容
- android gradle jnilibs
- python语言中的数据类型之列表