动态规划总结.doc

:从状态类型分,并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态,来解决问题。(长度)动态规划共性总结本类的状态是基础的基础,大部分的动态规划都要用到它,成为一个维。一般来说,有两种编号的状态:状态(i)表示前i个元素决策组成的一个状态。状态(i)表示用到了第i个元素,和其他在1到i-1间的元素,决策组成有的一个状态。题库a)最长不下降子序列以一元组(i)作为状态,表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n2)得算法。但本题可合理组织状态,引入一个单调的辅助数组,利用单调性二分查找,优化到O(nlogn)。关于优化详见优化章。一些问题可将数据有序化,转化成本题。应用:拦截导弹(NOIP99Advance1)就是原题。BeautifulPeople(sgu199),要将数据有序化:其中一个权作为第一关键字不下降排列,另一个权作为第二关键字不上升。Segment(ural1078),将线段的左端点有序化就可以了。b)LCS状态(i,j),表示第1个字符串的第i位,与第2个字符串的第j位匹配,得到的最长的串。若有多个串要LCS,则加维,即几个串就几个维。我也将此题归入路径问题。c)花店橱窗布置(IOI99)见路径问题。(占本类问题的30%)。题库a)石子合并见划分问题b)模版匹配(CEOI01,Patten)这题特殊的地方是状态的值是一个集合而不是一个数。c)不可分解的编码(ACMWorldFinal2002)d)ElectricPath(ural1143)e)邮局(IOI2000Day21)若状态表示的思路从第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是连续的,所以空间可以降维:f(i,j)表示放前i个邮局到前j个村庄的最优值。f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1}e(i,j)为当f(i,j),得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)决策数量又少了一个数量级。,状态是由坐标维与其他的维组成。本类与划分问题(是2维或多维的坐标系的划分)与路径问题的交集占本类问题中大多数。题库a)棋盘分割(NOI994)主要是将公式变形,变形后的公式很容易看出方程。状态是由2个坐标组成的4元组(x1,y1)(x2,y