dp的林林总总（持续更新，dp骚气解法等等）
2024-09-01 12:18:06
写在前面:
本人dp较弱，所以总结了一些坑点，转化思路以供复习使用，勿喷，甚至一些不是dp的题（贪心等等）也会放在这。
每个点后面会有我自己的题解，如果没有链接，向下找第一个链接，可能会有多题。
1、当有两人博弈时，先手最优可以转化为后手最劣（bzoj2101传送门）
2、一些骚气的dp可以直接转化为最短路（传送门usaco 2005 dec）：一般当状态不太好表示或者当一个状态能推到后面几个状态时
3、注意式子的变形（括号展开，乘之类的），可能能够优化
4、状态表示尽量向整体靠近，可以省略一些无用的枚举（传送门 [USACO10NOV]购买饲料 传送门）
5、单调栈优化：通常展开，找到要枚举的相对不变量，然后用单调栈维护它（通常代入方程式，判断最优的点），然后用栈顶更新最值。（传送门 [USACO10NOV]购买饲料，传送门）
6、对于一些复杂的状态，可以考虑拆分（比如四个方向表示的一维可以拆分成两个量的二维）（传送门P2905 [USACO08OPEN]农场危机）
7、我也不知道怎么描述这个技巧，莽就完了（传送门）
8、一些dp的方程（类似维护和，区间合并啊）可以用线段树支持合并（传送门P3097[USACO13DEC]最优挤奶）
9、计算方案数的时候，可以分开计算然后利用计数原理计算方案
10、关于dfs（或其它有关状态的东西）可以试着更换状态，所有的状态都试一试，可能会有意想不到的效果
11、dp完之后一定要考虑一下后效性，
最新文章
- 利用vmware 搭建分布式集群
- mybatis 的if else
- mysql in 排序
- [Design Patterns] 1. Primary concept & term - UML
- ASP.NET MVC Razor HtmlHelper扩展和自定义控件
- hadoop1.2.1的namenode格式化失败的问题
- Qt之SQL数据库
- mysql binlog 混合模式 出现的基于sql的数据不一致,主要是now()这类函数导致
- 【Bible for kids】 儿童圣经 App
- pip install -r requirements.txt 安装mysqldb失败 解决方案
- 2017ecjtu-summer training #7 POJ 2689
- Java枚举enum以及应用：枚举实现单例模式
- DataPipeline |《Apache Kafka实战》作者胡夕：Apache Kafka监控与调优
- tp5 整合 个推
- QPixmap 在非QtCreator环境下无法显示jpg图片
- LeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium
- Objective-C atomic属性不是线程安全的
- 研究js特效巩固JavaScript知识
- new命令简化的内部流程
- 微信 小程序组件 加入购物车全套 one wxml