第3章-动态规划-习题.pptVIP

最长单调递增子序列(习题3-1) 设计一个O(n2)时间的算法, 找出由n个数组成的序列的最长单调递增子序列。 输入 第1个整数n(0n100),表示后面有n个数据，全部为整数 输出 输出最长单调递增子序列的长度； 样例输入 8 65 158 170 155 239 300 207 389 样例输出 6 * 最多拦截导弹数/ShowProblem.aspx?ShowID=1278 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它能拦截任意高度的导弹，但是每拦截一发导弹，其拦截能力就下降到只能拦截上一次拦截的导弹高度。某天，雷达捕捉到敌国的导弹来袭，导弹依次飞来，该拦截系统最多能拦截多少导弹呢？ Input: 输入若干组数据。每组数据包括：导弹总个数（正整数1000），导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，用空格分隔）。若导弹个数为0，则处理结束。 Output: 输出这套系统最多能拦截多少导弹。 Sample Input: 8 3890 2070 1550 3000 2990 1700 1580 650 0 Sample Output: 6 * 最长单调递增子序列 用数组b[0:i]记录以a[i] (0≤in) 为结尾元素的最长递增子序列的长度。 序列a的最长递增子序列的长度为：max {b[i]} 显然，b[i]满足最优子结构性质，可以递归的定义为： b[0] = 1; b[i] = max {b[k]} + 1 即k在0~(i-1)范围内, 若a[k] ≤a[i], 寻找最大的b[k]. 据此将计算b[i]转化为i个规模更小的子问题。 0≤in 0≤ki a[k] ≤a[i] 65 158 170 155 239 300 207 389 1 2 3 2 4 5 4 6 i k * 最长单调递增子序列 int main() { int n; scanf(%d, n); int a[100]; for (int i=0; in; i++) scanf(%d, a[i]); printf(%d\n, LISdyna( a, n)); } 样例输入 8 65 158 170 155 239 300 207 389 * 最长单调递增子序列 int main() { int n; scanf(%d, n); int a[100]; for (int i=0; in; i++) scanf(%d, a[i]); printf(%d\n, LISdyna(a, n)); } int LISdyna(int a[ ], int n) { int b[100]={0}; int i,j; b[0] = 1; for (i=1;in; i++) { int k = 0; //0~i-1之间，b的最大值 for (j=0; ji; j++) if (a[j]=a[i] kb[j]) k=b[j]; b[i] = k+1; } int max = 0; for (i=0; in; i++) if (b[i]max) max = b[i]; return max; } * 字符串的编辑距离/ShowProblem.aspx?ShowID=1381 设s1和s2是两个字符串, 经过一些操作，我们可以将字符串s1转换为字符串s2, 这里所说的字符操作包括: (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符. 将字符串s1转换为字符串s2所用的最少字符操作数称为字符串s1到字符串s2的编辑距离, 它描述了s1和s2的近似程度. Input: 输入有多组,每组2行字符串,分别为s1,s2,均不为空,长度不大于1000. Output: 对于每组输入,输出最小编辑距离. Sample Input: abc ABC abc cba Sample Output: 3 2 * 编辑距离问题 设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括： 删除一个字符； 插入一个字符； 将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。 编程任务： 对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。 * 编辑距离问题 数据输入： 第一行是字符串A，第二行是字符串B。 结果输出: 程序运行结束时，输出编辑距离d(A,B) 。 输入文件示例 fxpimu xw