1、单调递增最长子序列
描述
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4
输入
第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7 2、最长公共子序列 描述 如题,需要写一个程序,得出最长公共子序列。 tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000. 输出 每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。 样例输入 2 asdf adfsd 123abc abc123abc 样例输出 3 6 3、括号匹配 时间限制:1000 ms | 内存限制:65535 KB 描述 给你一个字符串,里面只包含"(",")","[","]"四种符号,请问你需要至少添加多少个括号才能使这些括号匹配起来。 如: []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N,表示测试数据组数(N<=10) 每组测试数据都只有一行,是一个字符串S,S中只包含以上所说的四种字符, S的长度不超过100 输出 对于每组测试数据都输出一个正整数,表示最少需要添加的括号的数量。每组 测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2 4、完全背包 描述 直接说题意,完全背包定义有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。本题要求是背包恰好装满背包时,求出最大价值总和是多少。如果不能恰好装满背包,输出NO 输入 第一行:N 表示有多少组测试数据(N<7)。 接下来每组测试数据的第一行有两个整数M,V。M表示物品种类的数目,V 表示背包的总容量。(0 接下来的M行每行有两个整数c,w分别表示每种物品的重量和价值 (0 输出 对应每组测试数据输出结果(如果能恰好装满背包,输出装满背包时背包内物 品的最大价值总和。如果不能恰好装满背包,输出NO) 样例输入 2 1 5 2 2 2 5 2 2 5 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行,每行一个字符串,每个字符串长度不超过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(0 每组测试数据: 第一行有两个的整数r,c(0 随后有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 输出 输出蚂蚁能够摆出的最大的宽度。 样例输入 3 10 2 3 3 4 4 7 样例输出 9