第6周动态规划的优化slide40

1、TwIStOyMarch 10, 2015前言动态规划在解决问题的时候，利用的是保存中间状态来减少重复的计算次数的方法来减少时间消耗的。在很多问题中，动态规划的时间效率，或者空间复杂度都不能满足我们的要求（超出 我们的限制），这时候就要考虑对算法进行时间或者空间上的优化。前言动态规划问题总的来说还是对枚举的优化，即保存中间状态来减 少计算次数的方法。那么就可以大概的认为，一个动态规划问题 的时间复杂度应该是：时间复杂度 = 状态总数* 单个状态计算时间1单个状态计算时间 = 转移状态总数 * 转移时间我们只要减少其中的任何一个部分都可以达到式。动态规划的方1这只是直观的告诉了我们时间复杂度的构

2、成，而不能直接当作计算式。改进状态表示即通过改变状态的表示方式来减少状态总数的方法。这种方法通 常是一开始想出来的状态表示方法并不够好，还有我们没有发现 的关系或者条件。在这种时间，我们可以对状态的表示方法进行 优化，用一种更优的表示方法。这样在转义数量和转移时间不变 的情况下，时间复杂度就已经被减小了。例题 IRaucous RockersYou just inherited the rights to n previously unreleased songs recorded by the popular group Raucous Rockers. You plan to releas

3、e a set of m compact disks with a selection of these songs.Each disk can hold aum of t minutes of music, and a songcan not overlap from one disk to another. Since you are a classical music fan and have no way to judge the artistic merits of these songs, you decide on the following criteria for makin

4、g the selection:1. The songs will be recorded on the set of disks in the order of the dates they were written.2. The total number of songs included will beized.InputThe input consists of one line containing the values of n, t, and m(integer numbers) followed by a line containing a list of the length

5、例题 IIof n songs, t1, t2, . . . , tn ordered by the date they were writtenn(Each ti is less than t minites long andti > m × t.) Outputi=1The output, consitsts of one integer indicating the number ofsongs that, following the above selection criteria will t on m disks.Sample Input10 5 33, 5, 1,

6、 2, 3, 5, 4, 1, 1, 5Sample Output6例题 I题目大把 n 个数字，分成 m 组。每组的和不能大于 t。分组必须是有序的，并且保证所有的数字都是小于 t 的。求最多能把多少数字划入分组里。最初的分析这里我们用 wi 来表示第 i 个数的值，用 dp 来表示我们的结果数组。那么我们可以显然的得到一个状态表示：dpijk = x来表示前 i 个数字，分成 j 组，还多了 k 的时候，最多有多少个数字被划入了分组中。可以显然的得到，这里整个问题的最优解应该是 dpnm0。通过状态的表示，我们可以得到状态转移方程：例题 IImax(dpi jk wi, dpi 1jk)k

7、 wi, i 11dp ij kmax(dpi 1j 1t wi, dpi 1jkk < wi, i 1 )0 k < t0这样时间复杂度应该是 O(nmt) 的。因为总状态数是 O(nmt)， 每次状态转移的状态数为 O(1)，总时间为 O(nmt)。改进改进后的状态表示：dpij = (x, y)表示在前 i 中选 j 个所需要的最少的分组为 x 另外还需要 y。通过状态的表示，我们可以得到状态转移方程：dpij = min(dpi 1j, gi 1j 1 + wi)例题 III其中，(x, y) + wi = (x, y) 计算方法为：x = x, y = y + wiwi

8、t yx = x + 1, y = wi wi > t y时间复杂度从 O(nmt)，降到了 O(n2)。这里空间复杂度也同时降低了。决策的单调性·四边形不等式 I例题 1在一个操场上摆放着一排 n(n 2 × 103) 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。求出将 n 堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。决策的单调性·四边形不等式 I最初的分析2令每堆石子的个数为：d1 . . . n。我们可以得到最基础的状态表示：mij 来表示合并第 i 个到第 j

9、 个石子堆所获得的最小得分。得到了状态转移方程和边界条件：j l=imij = 0 i = jmij = minmik 1 + mkj +dli<kjj并且把最优解保存在 sijdl 部分可以用 中。（这里的l=iO(n2) 的时间复杂度预处理，这样直接就好了。）总的时间复杂度：O(n3)2这里最大得分和最小得分的思路是一样的。这里只取最小得分来说明问题。四边形不等式定理当函数 w(i, j) 满足w(i, j) + w(i, j) w(i, j) + w(i, j), i i j j时，函数 w 满足四边形不等式。定理当函数 w(i, j) 满足w(i, j) w(i, j), i i

10、 j j时，函数 w 关于区间包含关系单调。四边形不等式j在这个问题中。令 w(i, jdl，可以显然得到 w(i, j) 是满) =l=i足四边形不等式的，同时也满足区间包含关系单调。根据 m 的递推式：mij = minj<kjmik 1 + mkj + w(i, j)(1)对于满足四边形不等式的函数 w 这里我们要证明，会使 m 也满足四边形不等式。四边形不等式这里当 i = i 或者 j = j 的时候，不等式显然成立。I四边形不等式这里当 i = i 或者 j = j 的时候，不等式显然成立。当 i < i = j < j 时。原式可以简化为：mij + mj, j

11、 mij 的形式。II四边形不等式这里当 i = i 或者 j = j 的时候，不等式显然成立。当 i < i = j < j 时。原式可以简化为：IImij + mj, j mij 的形式。设这时候取到最优值时的 l = k。这里又分为两种情况，Ik j 和 k > j。只讨论前一种情况，因为后一种和前一种是镜像的。四边形不等式这里当 i = i 或者 j = j 的时候，不等式显然成立。当 i < i = j < j 时。原式可以简化为：IImij + mj, j mij 的形式。设这时候取到最优值时的 l = k。这里又分为两种情况，Ik j 和 k >

12、; j。只讨论前一种情况，因为后一种和前一种是镜像的。Imij + mjj = w(i, j) + mik 1 + mkj + mjj w(i, j) + mik 1 + mkj + mjj w(i, j) + mik 1 + mkj= mij四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同样要分情况 z y 和 z > y。还是只讨论前一种，后一种是相似的。四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同

13、样要分情况 z y 和 z > y。还是只讨论前一种，后一种是相似的。mij + mijI四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同样要分情况 z y 和 z > y。还是只讨论前一种，后一种是相似的。mij + mij= w(i, j) + miz 1 + mzj + w(i, j) + miy 1 + myjII四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同样要分情况 z y 和 z &g

14、t; y。还是只讨论前一种，后一种是相似的。mij + mij= w(i, j) + miz 1 + mzj + w(i, j) + miy 1 + myj w(i, j) + w(i, j) + miy 1 + miz 1 + mzj + myjI II四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同样要分情况 z y 和 z > y。还是只讨论前一种，后一种是相似的。mij + mij= w(i, j) + miz 1 + mzj + w(i, j) + miy 1 + myj w(i, j)

15、 + w(i, j) + miy 1 + miz 1 + mzj + myj w(i, j) + w(i, j) + miy 1 + miz 1 + myj + mzjI I II四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同样要分情况 z y 和 z > y。还是只讨论前一种，后一种是相似的。mij + mij= w(i, j) + miz 1 + mzj + w(i, j) + miy 1 + myj w(i, j) + w(i, j) + miy 1 + miz 1 + mzj + myj

16、I I I II w(i, j) + w(i, j) + miy 1 + miz 1 + myj + mzj= mij + mij四边形不等式当 i < i < j < j 的时候，设 l = y 时 mij 取最优值，同I理 z 对于 mij。这里同样要分情况 z y 和 z > y。还是只讨论前一种，后一种是相似的。mij + mij= w(i, j) + miz 1 + mzj + w(i, j) + miy 1 + myj w(i, j) + w(i, j) + miy 1 + miz 1 + mzj + myjI I I I II w(i, j) + w(i,

17、 j) + miy 1 + miz 1 + myj + mzj= mij + mij综上，mij 满足四边形不等式。四边形不等式其决策满足单调性，即：记 sij 为 mij 取最优值时的决策，有：sij sij + 1 si + 1j + 1, i j这里要证明一下上面的那个式子成立。(2)令：mkij = mik 1 + mkj + w(i, j)，要证明sij sij + 1，也就是证明对于所有的 i < k k j 且mk ij mkij，有：mk ij + 1 mkij + 1四边形不等式这里有一个更强的不等式，mkij mk ij mkij + 1 mk ij + 1mkij

18、+ mk ij + 1 mkij + 1 + mk ij即：展开得到：mkj + mkj + 1 mkj + mkj + 1这恰好是 k k j j + 1 时的四边形不等式的形式。所以，当 w 满足四边形不等式的时候，sij 的取值满足单调性。决策的单调性·四边形不等式这样我们就可以改写我们的状态转移方程了，因为我们的决策的 范围已经被缩小了。mij = 0mij = minsij1ksi+1jmik 1 + mkj + w(i, j)时间复杂度：O(n2)。i = j决策单调性·四边形不等式 IDescriptionThere is a straight highway

19、 with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identied with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the dierence of their intege

20、r coordinates.Post oces will be built in some, but not necessarily all of the villages. A village and the post oce in it have the same position. For building the post oces, their positions should be chosen so that the total sum of all distances between each village and its nearest post oce is minimu

21、m.决策单调性·四边形不等式 IIYou are to write a program which, given the positions of the villages and the number of post oces, computes the least possible sum of all distances between each village and its nearest post oce. InputYour program is to read from standard input. The rst line contains two integer

22、s: the rst is the number of villages V,1 V 300, and the second is the number of post oces P,1 P 30, P V. The second line contains V integers inincreasing order. These V integers are the positions of the villages. For each position X it holds that 1 X 10000.OutputThe rst line contains one integer S,

23、which is the sum of all distances between each village and its nearest post oce.Sample Input决策单调性·四边形不等式 III10 51 2 3 6 7 9 11 22 44 50Sample Output9决策单调性·四边形不等式这题简单的 DP 是可以通过的。不过如果把数据范围扩大了，就可以用上面说的四边形不等式优化去优化。略去证明，这道题直 接给出伪代码：1234567891011for i 1 to ndo dp1, i w1, is1, i 0for i 2 to ndo s

24、i, n + 1 nfor j n downto 1do for k si 1, j to sij + 1do if dpi, k + dpk + 1jthen dpi, j dpi, k + dpk + 1jreg kdpi, j dpi, j + wi, j决策单调性·斜率优化在说斜率优化之前，要先说一下另一个优化方式。当我们发现一 个 dp 的状态转移方程形如这样的形式的时候，dp(i) = f(j) + g(i)也就是说，一个 i 的结果可以化成一个于 i 无关的函数的和另一个只与 i 有关的形式的时候。我们可以对前面的和 i 无关的部分放在一个优先队列里，这样可以把本来 O

25、(n) 的查找代价，变成log n 的。但是这终归是一个非常理想的方程啊，实际问题中这种良心满满 的题目基本是没有的。所以一种把条件放的稍微弱一点的优化方 式，就是斜率优化。也是通过结果和决策的关系，发现决策有事 满足一些神奇的数量关系的。决策单调性·斜率优化 IDescriptionZero has an old printer that doesnt work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a lo

26、ng time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will costk(C ) + M2ii=1M is a const number.Now Zero want to kno

27、w the minimum cost in order to arrange the article perfectly.决策单调性·斜率优化 IIInputThere are many test cases. For each test case, There are twonumbers N and M in the rst line (0 n 500000,0 M 1000). Then, there are N numbers in the next 2 to N +1 lines. Input are terminated by EOF.OutputA single num

28、ber, meaning the mininum cost to print the article.Sample Input5 559575Sample Output230最初的分析状态表示：dpi 来表示，从第一个到第 i 个输出的最少花费。很容易得到状态转移方程：dpi = min0j<idpj + M + sumj + 1 . . . i2(3)这个的时间复杂度可以很显然的计算出来，是 O(n2) 的。显然， 我们是不能接受这种时间复杂度的，因为数据范围非常大。斜率优化 I这里，我们先假设，3式中的 j 取值为 k1 的时候，比取 k2 的时候更优。也就是：dpk1 + sumk1 + 1 . . . i2 < dpk2 + sumk2 + 1 . . . i2其中，这里我们可以预处理得到一个 sum 数组。那么：sumk1 + 1 . . . i = sumi sumk1，同理对于 k2 的部分。移项得到：(dpk1+sumk12)(dpk2+sumk22) < 2sumi(sumk1sumk2)(4)其中所有的项都是我们已经计算好得到了的。我们设f(i) = dpi + sumi2，g(i) = sumi。4可以化成： f(k1) f(k2)< 2sumi(