动态规划典型例题

《动态规划典型例题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1、单调递增最长子序列描述求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4输入第一行一个整数0

2、其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。输入第一行给出一个整数N(0

3、内存限制：65535KB描述给你一个字符串，里面只包含"(",")","[","]

4、"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如：[]是匹配的([])[]是匹配的((]是不匹配的([)]是不匹配的输入第一行输入一个正整数N，表示测试数据组数(N<=10)每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100输出对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行样例输入4[]([])[]((]([)]样例输出00324、完全背包描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可

5、用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO输入第一行：N表示有多少组测试数据（N<7）。接下来每组测试数据的第一行有两个整数M，V。M表示物品种类的数目，V表示背包的总容量。(0

6、好装满背包，输出装满背包时背包内物品的最大价值总和。如果不能恰好装满背包，输出NO）样例输入21522252251样例输出NO15、工程描述有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、行。样例输入1320112416样例输出186、回文字符串时间限制：3000ms

8、内存限制：65535KB描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。输入第一行给出整数N（0

9、出27、最大和时间限制：1000ms

10、内存限制：65535KB描述给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。例子：0-2-7092-62-41-41-180-2其最大子矩阵为：92-41-18其元素总和为15。输入第一行输入一个整数n（0

11、之和。样例输入1440-2-7092-62-41-41-180-2样例输出158、整数划分描述整数划分是一个经典的问题。请写一个程序,完成以下要求。输入每组输入是两个整数n和k。(1<=n<=50,1<=k<=n)输出对于输入的n,k;第一行：将n划分成若干正整数之和的划分数。第二行：将n划分成k个正整数之和的划分数。第三行：将n划分成最大数不超过k的划分数。第四行：将n划分成若干个奇