|
上节课我们留下了一个思考题：最长链的问题。 假设有一个包含很多个数字对的集合。在每一个数字对中，第一个数字小于第二个数字。比如，｛（1，3），（2，4），（6，7），（3，9），（4，5）｝。并且对于其中的任何两组数字对（a，b）和（c，d），如果b <c，则（c，d）可以接在（a，b）之后，形成（a，b）—>(c，d）的链条。用类似的方式，可以形成一个长链。请你找到可以形成的最长链。 例如，如果给定的对是{{5,24}，{39,60}，{15,28}，{27,40}，{50,90}}，那么可以形成的最长链是 长度为3，链为{{5,24}，{27,40}，{50,90}}。 最长链问题的解答 此问题是上节课最长递增序列（LIS）问题的变种。基于LIS问题的解法，我们给出解决最长链问题的两个简单步骤： 1）按照数对的第一个（或更小的）元素的递增顺序把数对进行排序。 2）执行下面的修改过的LIS过程：把已经完成的LIS的第二个元素与正在构造的新LIS的第一个元素进行比较。 下面是对应的C++实现代码例子。 #include <bits/stdc++.h> using namespace std; //记录数对的类Pair class Pair { public: int a; int b; }; //假设arr[]已经按照数对的第一个元素递增次序进行排序 int maxChainLength( Pair arr[], int n) { int i, j, max = 0; int *mcl = new int[sizeof( int ) * n ]; /* 对mcl (max chain length)数组中所有索引(i)的值进行初始化*/ for ( i = 0; i < n; i++ ) mcl[i] = 1; /* 自底向上计算对应的链的长度*/ for ( i = 1; i < n; i++ ) for ( j = 0; j < i; j++ ) if ( arr[i].a > arr[j].b && mcl[i] < mcl[j] + 1) mcl[i] = mcl[j] + 1; // mcl[i]现在记录了到第i个数对为止的最长链长 /* 从所有mcl值中选出最长的 */ for ( i = 0; i < n; i++ ) if ( max < mcl[i] ) max = mcl[i]; return max; } /*主程序 */ int main() { //注意这里的输入数对已经排好序了。 Pair arr[] = { {5, 24}, {15, 25}, {27, 40}, {50, 60} }; int n = sizeof(arr)/sizeof(arr[0]); cout << 'Length of maximum size chain is ' << maxChainLength( arr, n ); return 0; } 请你运行上述程序。 更多的同类问题
1）最大总和递增子序列 给定n个正整数的数组。编写程序查找给定数组的最大总和递增子序列：也就是子序列中的整数按递增顺序排序，并且该子序列中的所有整数之和为最大。例如，如果输入为{1,101,2,3,100,4,5}，则输出应为{1,2,3,100}。 2）造桥的问题 考虑有一条河流，从东流向西，穿过某个城市的中心地区。为方便交通，计划在河上修桥梁。假设河的南岸有n个候选位置，坐标为a(1)... a(n)，北岸有也有n个对应的候选位置，坐标为b(1)... b(n)。现在希望尽可能多地通过建立桥梁，将南北对应的位置连接起来：建立桥梁连接a(1)与b(1)、建立桥梁连接a(2)与b(2)、...、建立桥梁连接a(n)与b(n)。也就是说桥梁只能将北岸的位置b(i)连接到南岸的对应的位置a(i)，并且这些桥梁不能相互交叉。 请你找出满足上述条件的基础上，最多能建造多少座桥梁？ 上图中绿色的箭头表示修建的桥梁a(3)-b(3)、a(4)-b(4)和a(n)-b(n)。而a(1)和b(1)之间红色的箭头表示不能修建桥梁，因为会与其他已经修建的桥梁产生交叉。同样，a(2)和b(2)之间也不能修建桥梁。 3. 叠积木方块问题 假设有一组n个积木，每个积木的形状都是长方块：第i个积木高度为h(i)，宽度为w(i)，长度为l(i)，这里h(i),w(i)和l(i)都是正实数。 现在请您用这n个积木搭建一个尽可能高的积木堆，要求放在下面的积木块的底部的二维尺寸严格大于放在它上面的积木的二维尺寸。你只能在另一个积木的顶部放置积木块。当然，你随意可以旋转积木块，可以用积木块六面中的任何一面作为基础。 动态规划类型的题目，需要观察和寻找重叠的子问题以及最优的子结构，然后采用适当的方案进行解答。后面的课程中我们还会继续讲解一些例子。请大家用心体会。 |
|
|
