动态规划总结VIP免费

下载后可任意编辑动态规划总结by Amber1. 按状态类型分写在前面：从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态，来解决问题。1.1. 编号（长度）动态规划共性总结本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。一般来说，有两种编号的状态：状态(i)表示前 i 个元素决策组成的一个状态。状态(i)表示用到了第 i 个元素，和其他在 1 到 i-1 间的元素，决策组成有的一个状态。题库a) 最长不下降子序列以一元组(i)作为状态，表示第 i 个作为序列的最后一个点的时候的最长序列。于是很容易想到 O(n2)得算法。但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到 O(nlogn)。关于优化详见优化章。一些问题可将数据有序化，转化成本题。应用：拦截导弹(NOIP99 Advance 1) 就是原题。Beautiful People (sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。Segment (ural 1078)，将线段的左端点有序化就可以了。b) LCS状态(i,j)，表示第 1 个字符串的第 i 位，与第 2 个字符串的第 j 位匹配，得到的最长的串。若有多个串要 LCS，则加维，即几个串就几个维。我也将此题归入路径问题。c) 花店橱窗布置(IOI99)见路径问题。1.2. 区间动态规划共性总结本类问题与下一章的划分问题的决策的分割点无序交集比较大（占本类问题的 30%）。下载后可任意编辑题库a) 石子合并见划分问题b) 模版匹配(CEOI01,Patten)这题特别的地方是状态的值是一个集合而不是一个数。c) 不可分解的编码(ACM World Final 2024)d) Electric Path(ural1143)e) 邮局(IOI2000 Day2 1)若状态表示的思路从第 i 个村庄可以从属于哪个邮局，无最优子结构。转变一个方向：第 k 个邮局可以“控制”一个区间的村庄[i,j]。于是方程就显然了:f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1<=p<=i-1)S(i) 为村庄 i 到原点的距离。w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j]间最好的一个邮局点。不过可以发现 Sum{|S(k)-S(p)|是单调的，所以取中位数就可以了。即上式中 k 的取值范围只有 floor((i+j)/2), ceil((i+j)/2)两个。Floor 是下取整。Ceil 是上取整。这样每次转移时间降到 O(1)。注意到是区间连续的，即(p,i-1) 和(i, j) 中的 i-1, i 是连续的，所以空间可以降...