Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"nbyby","updateTime":1495463384000,"title":"我的一些DP理解_yby","dislikeCnt":0,"content":"### 我的理解\n\n+ 主题思想\n\t* 确定是否可以DP解决\n\t\t- 首先,自己不太明确类型的题(一般来说,计算几何,数据结构,数学,字符串,图论的一部分题能很容易一眼看出题目类型),很有可能是DP、网络流、或者乱搞。\n\t\t- 用DP来思考问题的话,首先就是能否设计出无后效性的状态(简单来说就说状态是一个DAG(有向无环图)图上的点,转移就是边),然后看能否满足复杂度。。。\n\t\t- 其实就是一个不断试错的过程。\n\t* 一般解决套路\n\t\t- 子问题的确立(有时候可以没有?我理解的不是很深刻)\n\t\t- 状态的确立(压缩状态数,看状态数是否足够)\n\t\t- 状态转移怎么转移?\n\t\t- 复杂度的计算,一般来说 复杂度\u003d状态数*转移复杂度\n\t\t- 复杂度不够的话,考虑能不能优化DP方程的转移。还是不行的话,重新确立状态。\n\t\t- 复杂度可以,考虑边界条件的处理\n\t\t- 考虑DP写法\n\t\t- 实现\n+ 两种常见的DP写法\n\t* 记忆化搜索(强烈建议熟练这种写法,非常好用)\n\t* 常规的递推(一般来说,要优化的话,只能对递推的形式进行优化)\n\t* 所以上述两种一般得都会\n+ DP几种套路题\n\t* 线性DP\n\t\t- 常规的LIS,LCS等\n\t\t- 一般理解具体的DP思想就好吧。\n\t* 背包DP\n\t\t- 几种典型背包,可见:背包九讲\n\t* 区间DP\n\t\t- 很套路的题,一般都是一眼题,建议使用记忆化搜索\n\t\t- 做过几个典型就全会了(可能只用一个?)\n\t\t- 记忆化搜很好写\n\t* 概率DP\n\t\t- 一般来说概率DP的套路也很固定。\n\t\t- 一般来说概率相关问题的解法,很多情况下和期望相关\n\t\t- 有的时候,会转化成解方程的形式,然后高斯消元\n\t\t- 这种类型的题也是做几个就全会了\n\t* 树形DP\n\t\t- 树形DP一般是在树上搞事情\n\t\t\t+ 插一嘴,树相关的题一般树形DP或者数据结构,别的题基本没有\n\t\t- 树形DP也有几种比较固定的状态的设计\n\t\t- 树形DP难的挺多的\n\t* 数位DP\n\t\t- 很套路的题,建议使用记忆化搜索\n\t\t- 解决的问题都是按数位处理(做过几题之后看到就知道是不是这个类型,一般来说看数据规模)\n\t* 状压DP\n\t\t- 很多比较难的题。。。或者说最难的题一般都与此相关\n\t\t- 主要的思想就是对状态按位压缩,一般是二进制,插头是三进制?\n\t\t- 按位压缩的状态压缩很关键\n\t* 连通性DP\n\t\t- 一般来说代码量比较大,也有套路,但是我其实不是很会orz。。\n\t\t- 插头DP\n\t\t\t+ 其中一种类型,代码量挺大,麻烦。。。我也不会\n\t* 博弈及其相关\n\t\t- 很多情况下,博弈其实也是状态转移,所以和DP很像的\n\t* 字符串及其相关\n\t\t- 一般来说,涉及到序列的题,都是DP。\n\t\t- 字符串的题都是那些字符串做法(后缀数组啥的)\n\t\t- 意思就是要不要求连续的\n\t* 其他比较难的套路\n\t\t- 几种计数DP\n\t\t\t+ 好多好多啊,一般经常会和数学结合在一起\n\t\t\t+ 组合数学相关题比较多。。\n\t\t\t+ 感觉能出的巨难。。。\n\t\t- DP套DP\n\t\t\t+ 难,但是有套路\n\t\t- 斯坦纳树\n\t\t\t+ spfa\n\t\t- 高维的题\n\t\t\t+ 我不会。。。\n+ DP优化套路\n\t* 矩阵快速幂\n\t\t- 一般对于一种线性递归方程,然后某一维很大的情况\n\t\t- 这种情况下,我们可以推出一个转移矩阵,然后就可以矩阵快速幂了\n\t* 斜率优化\n\t\t- 一种很常见的优化姿势\n\t\t- 运用到数形结合的思想\n\t\t- 做几道就有感觉了?\n\t* 平行四边形优化\n\t\t- 对二维状态的优化,题目比较少。。。\n\t\t- 我也没做过几道\n\t* 数据结构优化\n\t\t- 常见的有线段树优化等\n\t\t- 其他的见得不是很多\n\t* 状态不连续\n\t\t- 使用指针之类的?\n\t\t- map Hash\n\t* 计数的套路\n\t\t- 容斥\n\t\t- 数学相关知识\n\t* 黑科技\n\t\t- bitset\n\t\t\t+ 不要使用循环,不然效率很低下\n\t\t- 各种剪枝乱搞","likeCnt":3,"createTime":1495459736000,"isWorkbook":false,"viewCnt":1290,"openness":1,"fav":false,"id":128,"trustable":false}