《2022年动态规划典型例题 .pdf》由会员分享，可在线阅读，更多相关《2022年动态规划典型例题 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习好资料欢迎下载1、单调递增最长子序列描述求一个字符串的最长递增子序列的长度如： dabdbf 最长递增子序列就是abdf，长度为 4 输入第一行一个整数0n20, 表示有 n 个字符串要处理随后的 n 行，每行有一个字符串，该字符串的长度不会超过10000 输出输出字符串的最长递增子序列的长度样例输入3 aaa ababc abklmncdefg 样例输出1 3 7 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载2、最长
2、公共子序列描述如题，需要写一个程序，得出最长公共子序列。tip ：最长公共子序列也称作最长公共子串(不要求连续) ，英文缩写为LCS（Longest Common Subsequence） 。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。输入第一行给出一个整数N(0N100)表示待测数据组数接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000. 输出每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。样例输入2 asdf adfsd 123abc abc123abc 样例输出3
3、 6 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载3、括号匹配时间限制： 1000 ms | 内存限制： 65535 KB 描述给你一个字符串，里面只包含(,),四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如： 是匹配的()是匹配的( 是不匹配的() 是不匹配的输入第一行输入一个正整数N，表示测试数据组数(N=10) 每组测试数据都只有一行，是一个字符串S，S 中只包含以上所说的四种字符，S的长度不超过
4、100 输出对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行样例输入4 () ( () 样例输出0 0 3 2 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载4、完全背包描述直接说题意， 完全背包定义有N 种物品和一个容量为V 的背包， 每种物品都有无限件可用。第 i 种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量， 且价值总和最大。 本题要求是背包恰
5、好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出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 精品资料 - - - 欢迎下载 - - - - - -
6、 - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载5、工程描述有 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; 输出输出最
7、短时间，占一行。样例输入1 3 20 1 1 2 4 1 6 样例输出18 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载6、回文字符串时间限制： 3000 ms | 内存限制： 65535 KB 描述所谓回文字符串， 就是一个字符串， 从左到右读和从右到左读是完全一样的，比如 aba 。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以
8、使这个字符串成为回文字符串。输入第一行给出整数N（0N100 ）接下来的 N 行，每行一个字符串，每个字符串长度不超过1000. 输出每行输出所需添加的最少字符数样例输入1 Ab3bd 样例输出2 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载7、最大和时间限制： 1000 ms | 内存限制： 65535 KB 描述给定一个由整数组成二维矩阵（r*c） ，现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大， 并
9、把这个子矩阵称为最大子矩阵。例子：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 2 -4 1 -4 1 -1 8 0 -2 样例输出15 8、整数划分描述精品资料 - - - 欢迎下载 - - - - - - - - -
10、 - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载整数划分是一个经典的问题。请写一个程序,完成以下要求。输入每组输入是两个整数n 和 k。(1 = n = 50, 1 = k = n) 输出对于输入的n,k; 第一行：将 n 划分成若干正整数之和的划分数。第二行：将 n 划分成 k 个正整数之和的划分数。第三行：将 n 划分成最大数不超过k 的划分数。第四行：将 n 划分成若干个奇正整数之和的划分数。第五行：将 n 划分成若干不同整数之和的划分数。第六行：打印一个空行样例输入5 2 样例输出7
11、 2 3 3 3 提示样例输出提示 : 1. 将 5划分成若干正整数之和的划分为：5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 2.将5划分成 2个正整数之和的划分为：3+2, 4+1 3.将5划分成最大数不超过2的划分为：1+1+1+1+1, 1+1+1+2, 1+2+2 4.将5划分成若干奇正整数之和的划分为：5, 1+1+3, 1+1+1+1+1 5.将5划分成若干不同整数之和的划分为：5, 1+4, 2+3 9、蚂蚁的难题时间限制： 2000 ms | 内存限制： 65535 KB 描述蚂蚁是一个古玩爱好者，他收藏了很多瓶瓶罐罐。有一天，他
12、要将他的宝贝们一字排开，摆放到一个长度为L 的展台上。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 10 页 - - - - - - - - - - 学习好资料欢迎下载已知他有 n 件宝贝，每件宝贝的宽为w,由于这些瓶瓶罐罐的形状特殊，所以在摆放时需要至少 X 的宽度来摆放他们， （仅摆放时需要X 的宽度，摆放后宽度仍为w）现在已知了每件宝贝的宽度wi，和摆放它们所需的宽度Xi。请你帮蚂蚁计算一下，在这个展台上，他最多能摆多宽的宝贝。输入有多组测试数据。对于每一组测试数据：第一行：n L 分
13、别代表有n 件宝贝，展台长度为L;(n1000, L10000) 接下来有 n 行, 每行有两个整数wi xi 分别代表第i 件宝贝的宽度和摆放时需要的宽度。（0wi = xi 10000）. 输出输出蚂蚁能够摆出的最大的宽度。样例输入3 10 2 3 3 4 4 7 样例输出9 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 10 页 - - - - - - - - - - 文档编码：KDHSIBDSUFVBSUDHSIDHSIBF-SDSD587FCDCVDCJUH 欢迎下载 精美文档欢迎下载 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 10 页 - - - - - - - - - -