才开始呢!
1.树形DP(可以说是基本掌握了)
-递归实现
-多叉转二叉(也有不转直接当图做的)
-缩环成点(结合图论)
=选课
=无上司的舞会
=
旅游路线
=约束背包
=最优子树
=树的路径(这方面还要研究一下)
【结合 LCA求树上两点直接距离之类的】
【还要树的性质的应用】
2.贪心DP(应该都会了吧)
-排序
-部分使用贪心策略
=养猪
=
产品排序 =Ticket Office
3.单调DP+四边形不等式
-会证明决策单调性。
-二分找到类似二次函数那样的拐点
-分离变量和常量
-数形结合,转换成一次函数的斜率
=经典试题:最长限制字段和、多重背包(有点晕)
=USACO的那道题
=论文上的几道题(没有完全解决)
4.状态压缩DP
-描述状态,适当转移
-用类似于回溯的方式生成状态,并转移。
=铺地砖1
=骑士覆盖
=铺地砖2
5.数学统计DP
-方法不是很好总结,就是联想到数字的一些性质,有时候就是把数按位拆开看。
=SCOI2009.d1.t1 Windy数
=SCOI2009.d2.t2
=AHOI2009.d1.t2(未解决)
6.组合DP
-利用加法原理、乘法原理和组合公式做。
=POJ.DP练习赛上的题目(未解决)
=AHOI2009.d2.t2
7.图的DP
-那一类经过k条边的路径数。
-上面那题的变形,要拆点。
-矩阵优化
=经典试题
=SCOI2009.d2.t3
8.构造类DP
-用状态构造方程
-用方程生成状态
=count
=twofive
=数学与程序设计上的一些题