没有合适的资源?快使用搜索试试~ 我知道了~
动态规划总结-by Amber.doc
需积分: 10 176 下载量 83 浏览量
2007-09-05
18:39:27
上传
评论 1
收藏 95KB DOC 举报
温馨提示
试读
8页
动态规划总结byAmber
资源推荐
资源详情
资源评论
[ADN.cn][Library]Summary 动态规划总结 by Amber
动态规划总结
by Amber
1. 按状态类型分
写在前面:
从状态类型分,并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好
几种方法组合成一个状态,来解决问题。
1.1. 编号(长度)动态规划
共性总结
本类的状态是基础的基础,大部分的动态规划都要用到它,成为一个维。
一般来说,有两种编号的状态:
状态(i)表示前 i 个元素决策组成的一个状态。
状态(i)表示用到了第 i 个元素,和其他在 1 到 i-1 间的元素,决策组成有的一个状态。
题库
a) 最长不下降子序列
以一元组(i)作为状态,表示第 i 个作为序列的最后一个点的时候的最长序列。于是
很容易想到 O(n
2
)得算法。但本题可合理组织状态,引入一个单调的辅助数组,利用单
调性二分查找,优化到 O(nlogn)。关于优化详见优化章。
一些问题可将数据有序化,转化成本题。
应用:
拦截导弹(NOIP99 Advance 1) 就是原题。
Beautiful People (sgu199),要将数据有序化:其中一个权作为第一关键字不下降排
列,另一个权作为第二关键字不上升。
Segment (ural 1078),将线段的左端点有序化就可以了。
b) LCS
状态(i,j),表示第 1 个字符串的第 i 位,与第 2 个字符串的第 j 位匹配,得到的最
长的串。若有多个串要 LCS,则加维,即几个串就几个维。我也将此题归入路径问题。
c) 花店橱窗布置(IOI99)
见路径问题。
1.2. 区间动态规划
共性总结
第 1 页 共 8 页
1
资源评论
wizardblue2
- 粉丝: 3
- 资源: 31
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功