当前位置:首页 >> 数学 >>

动态规划典型例题


1、单调递增最长子序列
描述
求一个字符串的最长递增子序列的长度 如:dabdbf 最长递增子序列就是 abdf,长度为4

输入
第一行一个整数0<n<20,表示有 n 个字符串要处理 随后的 n 行,每行有一个字符串,该字符串的长度不会超过10000

输出
输出字符串的最长递增子序列的长度

样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7

2、最长公共子序列 描述
如题,需要写一个程序,得出最长公共子序列。 tip :最长公共子序列也称作最长公共子串 ( 不要求连续 ) ,英文缩写为 LCS ( Longest Common Subsequence) 。其定义是,一个序列 S ,如果分别是两个或多个已知序列的 子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

输入
第一行给出一个整数 N(0<N<100)表示待测数据组数 接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000.

输出
每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。

样例输入
2 asdf adfsd 123abc abc123abc

样例输出
3 6

3、括号匹配
时间限制:1000 ms | 内存限制:65535 KB

描述
给你一个字符串,里面只包含"(",")","[","]"四种符号,请问你需要至少添加多少个括号 才能使这些括号匹配起来。 如: []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的

输入
第一行输入一个正整数 N,表示测试数据组数(N<=10) 每组测试数据都只有一行,是一个字符串 S,S 中只包含以上所说的四种字符, S 的长度不超过100

输出
对于每组测试数据都输出一个正整数,表示最少需要添加的括号的数量。每组 测试输出占一行

样例输入
4 [] ([])[] ((] ([)]

样例输出
0 0 3 2

4、完全背包
描述
直接说题意,完全背包定义有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。 第 i 种物品的体积是 c,价值是 w。求解将哪些物品装入背包可使这些物品的体积总和不超 过背包容量, 且价值总和最大。 本题要求是背包恰好装满背包时, 求出最大价值总和是多少。 如果不能恰好装满背包,输出 NO

输入
第一行: N 表示有多少组测试数据(N<7) 。 接下来每组测试数据的第一行有两个整数 M,V。 M 表示物品种类的数目,V 表示背包的总容量。(0<M<=2000,0<V<=50000) 接下来的 M 行每行有两个整数 c,w 分别表示每种物品的重量和价值 (0<c<100000,0<w<100000)

输出
对应每组测试数据输出结果(如果能恰好装满背包,输出装满背包时背包内物 品的最大价值总和。 如果不能恰好装满背包,输出 NO)

样例输入
2 1 2 2 2 5

5 2 5 2 1

样例输出
NO 1

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;

输出
输出最短时间,占一行。

样例输入
1 3 20 1 1 2 4 1 6

样例输出
18

6、回文字符串
时间限制:3000 ms | 内存限制:65535 KB

描述
所谓回文字符串, 就是一个字符串, 从左到右读和从右到左读是完全一样的, 比如"aba"。 当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你, 给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成 为回文字符串。

输入
第一行给出整数 N(0<N<100) 接下来的 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 其最大子矩阵为: 92 -4 1 -1 8 其元素总和为15。 输入
第一行输入一个整数 n(0<n<=100),表示有 n 组测试数据; 每组测试数据: 第一行有两个的整数 r,c(0<r,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、整数划分
描述
整数划分是一个经典的问题。请写一个程序,完成以下要求。

输入
每组输入是两个整数 n 和 k。(1 <= n <= 50, 1 <= k <= n)

输出
对于输入的 n,k; 第一行: 将 n 划分成若干正整数之和的划分数。 第二行: 将 n 划分成 k 个正整数之和的划分数。 第三行: 将 n 划分成最大数不超过 k 的划分数。 第四行: 将 n 划分成若干个 奇正整数之和的划分数。 第五行: 将 n 划分成若干不同整数之和的划分数。 第六行: 打印一个空行

样例输入
5 2

样例输出
7 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

描述
蚂蚁是一个古玩爱好者,他收藏了很多瓶瓶罐罐。 有一天,他要将他的宝贝们一字排开, 摆放到一个长度为 L 的展台上。 已知他有 n 件宝贝, 每件宝贝的宽为 w,由于这些瓶瓶罐罐的形状特殊,所以在摆放时需要 至少 X 的宽度来摆放他们, (仅摆放时需要 X 的宽度, 摆放后宽度仍为 w)现在已知了每 件宝贝的宽度 wi,和摆放它们所需的宽度 Xi。请你帮蚂蚁计算一下,在这个展台上,他最 多能摆多宽的宝贝。

输入
有多组测试数据。 对于每一组测试数据: 第一行: n L 分别代表有 n 件宝贝,展台长度为 L;(n<1000, L<10000) 接下来有 n 行, 每行有两个整数 wi xi 分别代表第 i 件宝贝的宽度和摆放时需要 的宽度。 (0<wi <= xi < 10000).

输出
输出蚂蚁能够摆出的最大的宽度。

样例输入
3 2 3 4 10 3 4 7

样例输出
9


赞助商链接
相关文章:
最大字段和问题 动态规划法
最大字段和问题 动态规划法_数学_自然科学_专业资料。算法分析与设计 淮海工学院计算机工程学院 实验报告书课 程名:题目: 《算法分析与设计》 实验 2 动态规划...
更多相关标签: