北京大学ACM国际大学生程序设计竞赛(2)ppt课件

1、问题求解与程序设计第六讲 动态规划内容提要 3.27-4.3一周不上课做出题作业 动态规划 A decorative fence - 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个数存起来，每次只用一个加法 Fn = Fn-1+Fn-2 即可。问题A decorative fence1037问题的出处 中欧信息学奥林匹克竞赛

2、 2002年6月30日-7月6日 第一天: fence A decorative fence 时限: 1 s 内存: 1 MB问题描画美丽的篱笆定义如下：篱笆由宽度一样，高度互不一样的木条组成组成篱笆的木条高低相间，参差有致篱笆的长度定义为组成篱笆的木条数目N，其中木条的高度取值不按陈列顺序分别为1，2，N。把篱笆按其木条高度顺序记为：a1a2aN，那么可以对篱笆进展字典排序，例如： 问题描画长度为 4 的美丽篱笆排序为： 1 2 3 4 5 6 7 8 9 10 问题描画 给定篱笆长度给定篱笆长度N和在该长度下的序号和在该长度下的序号C，要求，要求给出第给出第C中美丽篱笆的外形。中美丽篱笆的

3、外形。问题描画样例输入：22 13 3样例输出：1 22 3 1样例解释1212132132132132问题解答 问题分析 对于长度为N的美丽篱笆，其序列为： 以高度为1的木条开场的上升序列 以高度为2的木条开场的下降序列 以高度为2的木条开场的上升序列 以高度为3的木条开场的下降序列 以高度为3的木条开场的上升序列 问题解答 问题分析 假设可以确定上述每一种序列的个数，就可以确定数字C落在哪个区间，从而确定其第一个木条的高度；那么此时问题简化成N-1规模的问题，按照同样的方法可以确定第2个木条的高度，以此类推，可以确定一切木条的高度。问题解答 递推公式 令 表示长度为N的美丽篱笆中以高度为i

4、的木条开场，呈下降趋势的篱笆的个数； 令 表示长度为N的美丽篱笆中以高度为i的木条开场，呈上升趋势的篱笆的个数； 那么有公式：downiNT,upiNT,问题解答downiNNupiNTT1,123公式解释 公式1：以1开场的下降序列为0个 公式2：可以由下降序列的个数推出上升序列的个数，如以下图：公式解释ix1x2x3x4x5x6x7N+1N-i+1iiiiiiiN-i+1公式解释 公式3：在以j+1开场的下降序列中，第2个木条的能够取值是1,j;以它开场的序列是上升序列，如以下图：公式解释j+11,2,jgoing downgoing up问题解答 根据递推公式可以生成两个数组up和dow

5、n数组，如下：11120012000200000000011200120002updown N=1 N=2 N=3 N=4 N=1 N=2 N=3 N=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难度问题。动态规划小结 递推公式 存储