dp的林林总总(持续更新,dp骚气解法等等)

写在前面:

本人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完之后一定要考虑一下后效性,要不然有些题目的状态的转移没法进行

12、注意可以用前缀和优化方案统计

13、要时刻想着一些模板(背包啊,最长不下降子序列啊),一些转化可以套用

14、一定要注意手推式子,玩式子真的非常重要

15、树上题目不要老是想着树形dp,状态太难转移,要考虑暴搜或是转化

16、记得平移下标(p2340奶牛会展)

原文地址:https://www.cnblogs.com/ajmddzp/p/11341118.html