北京大学ACM国际大学生程序设计竞赛课件6

问题求解与程序设计第六讲动态规划李文新2004.2–2004.6内容提要�3.27-4.3一周不上课做出题作业�动态规划�Adecorativefence-1037�动态规划小结�讨论–1014动态规划�与递归程序相类，将对问题求解分解为对子问题求解；不同之处在于把子问题的解存起来，用空间换时间。�例：Fibonacci数•F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);•递归:F(n-1)和F(n-2)分别求到底一次•动态规划：用数组将前n-1个数存起来，每次只用一个加法F[n]=F[n-1]+F[n-2]即可。问题Adecorativefence1037问题的出处�中欧信息学奥林匹克竞赛�2002年6月30日-7月6日�第一天:fence�Adecorativefence�时限:1s�内存:1MB问题描述漂亮的篱笆定义如下：�篱笆由宽度相同，高度互不相同的木条组成�组成篱笆的木条高低相间，错落有致�篱笆的长度定义为组成篱笆的木条数目N，其中木条的高度取值（不按排列顺序）分别为1，2，…，N。�把篱笆按其木条高度顺序记为：a1a2…aN，则可以对篱笆进行字典排序，例如：问题描述长度为4的漂亮篱笆排序为：12345678910问题描述给定篱笆长度N和在该长度下的序号C，要求给出第C中漂亮篱笆的形状。问题描述样例输入：22133样例输出：12231样例解释1212132132132132问题解答�问题分析�对于长度为N的漂亮篱笆，其序列为：•以高度为1的木条开始的上升序列•以高度为2的木条开始的下降序列•以高度为2的木条开始的上升序列•以高度为3的木条开始的下降序列•以高度为3的木条开始的上升序列•……问题解答�问题分析•如果能够确定上述每一种序列的个数，就可以确定数字C落在哪个区间，从而确定其第一个木条的高度；则此时问题简化成N-1规模的问题，依照同样的方法可以确定第2个木条的高度，以此类推，可以确定所有木条的高度。问题解答�递推公式•令表示长度为N的漂亮篱笆中以高度为iiii的木条开始，呈下降趋势的篱笆的个数；•令表示长度为N的漂亮篱笆中以高度为iiii的木条开始，呈上升趋势的篱笆的个数；•则有公式：downiNT,upiNT,问题解答downiNNupiNTT−+=1,,（1）（2）（3）公式解释�公式（1）：以1开始的下降序列为0个�公式（2）：可以由下降序列的个数推出上升序列的个数，如下图：公式解释ix1x2x3x4x5x6x7N+1N-i+1iiiiiiiN-i+1公式解释�公式（3）：在以j+1开始的下降序列中，第2个木条的可能取值是1,…,j;以它开始的序列是上升序列，如下图：公式解释j+11,2,…,jgoingdowngoingup问题解答�根据递推公式可以生成两个数组up和down数组，如下：00002000210021112000210021100000updownN=1N=2N=3N=4N=1N=2N=3N=4i=1i=2i=3i=4i=1i=2i=3i=4问题解答�对于长度为N的漂亮篱笆，可以查表得到序列：•以高度为1的木条开始的上升序列的个数n1•以高度为2的木条开始的下降序列的个数n2•以高度为2的木条开始的上升序列的个数n3•以高度为3的木条开始的下降序列的个数n4•以高度为3的木条开始的上升序列的个数n5•……问题解答这样就可以根据给出的序号C,判断它落在哪一个序号区间，从而得知它的第一根木条的高度，去除第一根木条，余下的问题就是一个N-1难度的问题，可以使用同样的方法求解，直到最后一根木条的高度被确定，整个问题就解决了。问题解答这里需要注意的是，去掉第一根木条后，余下的木条中比第一根木条高的木条的高度要减一，才是完全的N-1难度问题。动态规划小结�递推公式�存储结构及内容定义�计算顺序�从存储结构中还原问题的解讨论�Dividing1014作业�Dividing1014�Adecorativefence1037提高