动态规划典型例题

1、学习好资料欢迎下载1、单调递增最长子序列描述求一个字符串的最长递增子序列的长度女口： dabdbf最长递增子序列就是 abdf,长度为4输入第一行一个整数0n20,表示有n个字符串要处理 随后的n行，每行有一个字符串，该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3aaaababcabkl mn cdefg样例输出2、最长公共子序列描述如题，需要写一个程序，得出最长公共子序列。tip :最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS( LongestCommon Subsequenee )。其定义是，一个序列S，如果分别是两个或多个已知序列的子序

2、列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。输入第一行给出一个整数N(0N100)表示待测数据组数接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.输出每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。样例输入2 asdf adfsd 123abc abc123abc样例输出3、括号匹配时间限制：1000 ms |内存限制：65535 KB描述给你一个字符串，里面只包含(,),四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如：是匹配的()是匹配的(是不匹配的()是不匹配的输入第一行输入一个正整数N,表示测试数据组

3、数(N=10)每组测试数据都只有一行，是一个字符串S, S中只包含以上所说的四种字符,S的长度不超过100输出对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组 测试输出占一行样例输入4()()样例输出00324、完全背包描述直接说题意，完全背包定义有 N种物品和一个容量为 V的背包，每种物品都有无限件可用。 第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超 过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。 如果不能恰好装满背包，输出NO输入第一行：N表示有多少组测试数据(N7 )。接下来每组测试数据的第一行有

4、两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0M=2000 ，0V=50000)接下来的M行每行有两个整数c， w分别表示每种物品的重量和价值(0c100000，0w100000)输出对应每组测试数据输出结果(如果能恰好装满背包，输出装满背包时背包内物 品的最大价值总和。如果不能恰好装满背包，输出NO)样例输入21 52 22 52 25 1样例输出NO15、工程描述有n个工人做两个工程 A和B,每个工程都被分为相同的m份，给你第i个工人做A中的一份需要的时间 Xi秒，和做B中的一份所需时间 Yi秒，问最短需要多少时间可以完 成这两项工程。输入第一行是一个整数t (1 = t

5、 = 100), 表示有t组测试数据；每组测试数据第一行有两个整数n (1 = n = 100), m (1 = m = 100).接下来的n行，每行有两个整数 Xi,Yi;输出输出最短时间，占一行。样例输入3 201 66、回文字符串时间限制：3000 ms |内存限制：65535 KB描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如aba。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你， 给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成 为回文字符串。输入第一行给出整数 N (0N100)接下来的N行，每行

6、一个字符串，每个字符串长度不超过1000.输出1Ab3bd样例输出7、最大和时间限制：1000 ms |内存限制：65535 KB描述给定一个由整数组成二维矩阵(r*c)，现在需要找出它的一个子矩阵，使得这个 子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。例子：0 -2 -70 9 2 -6 2 -4 1 -4 1 -1 8 0 -2其最大子矩阵为：9 2 -4 1-1 8其元素总和为15。输入第一行输入一个整数 n ( 0*=100 ),表示有n组测试数据；每组测试数据：第一行有两个的整数 r，c( 0r,c=100 )，r、c分别代表矩阵的行和列；随后有r行，每行有c个整数；输

7、出输出矩阵的最大子矩阵的元素之和。样例输入14 40 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -28、整数划分描述整数划分是一个经典的问题。请写一个程序，完成以下要求。输入每组输入是两个整数n和k。(1 = n = 50, 1 = k = n)输出对于输入的n,k;第一行将n划分成若干正整数之和的划分数。第二行将n划分成k个正整数之和的划分数。第三行将n划分成最大数不超过 k的划分数。第四行将n划分成若干个奇正整数之和的划分数。第五行将n划分成若干不冋整数之和的划分数。第八仃打印一个空行样例输入2333提示样例输出提示：1. 将5划分成若干正整数之和的划分为：5, 4+1

8、, 3+2, 3+1+1,2+2+1, 2+1 + 1 + 1,1+1+1+1+12. 将5划分成2个正整数之和的划分为：3+2, 4+13. 将5划分成最大数不超过 2的划分为：1+1+1 + 1 + 1, 1 + 1 + 1+2, 1+2+24. 将5划分成若干 奇正整数之和的划分为：5, 1+1+3, 1+1 + 1 + 1+15. 将5划分成若干不同整数之和的划分为：5, 1+4, 2+39、蚂蚁的难题时间限制：2000 ms |内存限制：65535 KB描述蚂蚁是一个古玩爱好者，他收藏了很多瓶瓶罐罐。有一天，他要将他的宝贝们一字排开,摆放到一个长度为 L的展台上。已知他有n件宝贝，每件宝贝的宽为w,由于这些瓶瓶罐罐的形状特殊，所以在摆放时需要至少X的宽度来摆放他们，(仅摆放时需要 X的宽度，摆放后宽度仍为 w)现在已知了每件宝贝的宽度 wi，和摆放它们所需的宽度Xi。请你帮蚂蚁计算一下，在这个展台上，他最多能摆多宽的宝贝。输入有多组测试数