动态规划典型例题.doc

单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0n20,表示有n个字符串要处理随后的n行，每行有一个字符串，该字符串的长度不会超过10000 输出 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7 最长公共子序列 描述 如题，需要写一个程序，得出最长公共子序列。tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0N100)表示待测数据组数接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000. 输出 每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。 样例输入 2 asdf adfsd 123abc abc123abc 样例输出 3 6 括号匹配 时间限制：1000 ms | 内存限制：65535 KB 描述 给你一个字符串，里面只包含(,),[,]四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如：[]是匹配的([])[]是匹配的((]是不匹配的([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N=10)每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100 输出 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 0 0 3 2 完全背包 描述 直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO 输入 第一行： N 表示有多少组测试数据（N7）。 接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0M=2000，0V=50000)接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0c100000，0w100000) 输出 对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO） 样例输入 2 1 5 2 2 2 5 2 2 5 1 样例输出 NO 1 工程 描述 有n个工人做两个工程A和B，每个工程都被分为相同的m份，给你第i个工人做A中的一份需要的时间Xi秒，和做B中的一份所需时间Yi秒，问最短需要多少时间可以完成这两项工程。 输入 第一行是一个整数t (1 = t = 100),表示有t组测试数据;每组测试数据第一行有两个整数 n (1 = n = 100), m (1 = m = 100).接下来的n行,每行有两个整数Xi,Yi; 输出 输出最短时间，占一行。 样例输入 1 3 20 1 1 2 4 1 6 样例输出 18 回文字符串 时间限制：3000 ms | 内存限制：65535 KB 描述 所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如aba。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。 输入 第一行给出整数N（0N100）接下来的N行，每行一个字符串，每个字符串长度不超过1000. 输出 每行输出所需添加的最少字符数 样例输入 1 Ab3bd 样例输出 2 7、最大和 时间限制：1000 ms | 内存限制：65535 KB 描述 给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。 例子：0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩阵为： 9 2 -4 1 -1 8 其元素总和为15。 输入 第一行输入一个整数n（0n=100）,表示有n组测试数据；每组测试数据：第一行有两个的整数r，c（0r,c=100），r、c分别代表矩阵的行和列；随后有r行，每行有c个整数； 输出 输出矩阵的最大子矩阵的元素之和。 样例输入 1 4 4 0 -2 -7 0 9 2 -6