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
[]
([])[]
((]
([)]
样例输出
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 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<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
其最大子矩阵为：
9 2
-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 10
2 3
3 4
4 7
样例输出
9。