c++&oi

DP总结

才开始呢!
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 
   =数学与程序设计上的一些题

posted on 2012-03-30 23:36 zyn.cpp 阅读(334) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜