dp优化简单总结
2024-09-26 20:06:07
1.二分优化 (使用二分查找优化查找效率)
典型例题:LIS
dp[i]保存长度为 i 的上升子序列中最小的结尾,可以用二分查找优化到nlogn
2.数学优化 (通过数学结论减少状态数)
例题1:hdu4623
题解:http://www.cnblogs.com/oneshot/p/4064852.html
大意是求10个数及其倍数最大不能表示的数
有数论结论证明对于互质的p,q,最大不能表示的数不会超过p*q,所以这个题就成了有上限(256*256)的问题了,在上限内跑背包即可。
3.矩阵优化(通过矩阵快速幂加速状态转移)
......
4.单调队列优化 (在某些满足单调性的题中可以把复杂度直接降一维)
例题1:hdu3401
题解:http://www.cnblogs.com/oneshot/p/4057310.html
例题2:poj1821
思路跟上题差不多,dp[i][j]表示第 i 个人,最后一块是 j 的最大值,也是移项以后构建单调队列。。
例题3:poj1742 (多重背包,楼教主男人八题之一)
题解:http://www.cnblogs.com/oneshot/p/4062634.html
5.斜率优化
......
6.四边形优化
......
7.其他数据结构优化
挖坑待填......
最新文章
- Java 中的集合接口——List、Set、Map
- Greenplum-概念篇
- Python中使用递归输出嵌套列表并转化为大写
- 第一篇:初识bootstrap
- LDO和DC-DC器件的区别
- Hibernate 缓存介绍
- 使用socket.io开发简单群聊功能
- 帮初学者改代码——有多少青春可以挥霍之“c语言 多重排序”
- IOS开发之后台处理
- android Studio gradle so的加载
- 第一次写python
- C语言简短程序gcc编译过程
- [Hapi.js] Route parameters
- 【SPOJ839】Optimal Marks 网络流
- 09 ExpanableListView 的代码例子
- Java同步简介
- 马凯军201771010116《面向对象与程序设计Java》
- sed 笔记
- 菜鸟入门【ASP.NET Core】11:应用Jwtbearer Authentication、生成jwt token
- 廖雪峰Java6IO编程-1IO基础-1IO简介