【题目描述】

一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。

【输入描述】

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；

第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

【输出描述】

仅一行，一个数，表示最大总价值。

【样例输入】

10 4  2 1  3 3  4 5  7 9

【样例输出】

12

【题目描述】

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。

比如，如下4 × 4的矩阵

0  -2 -7  0  9  2 -6  2  -4  1 -4  1  -1  8  0 -2

的最大子矩阵是

9 2  -4 1  -1 8

这个子矩阵的大小是15。

【输入描述】

输入是一个N×N的矩阵。输入的第一行给出N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。

【输出描述】

输出最大子矩阵的大小。

【样例输入】

4  0 -2 -7  0  9  2 -6  2  -4  1 -4  1  -1  8  0 -2

【样例输出】

15

【题目描述】

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

【输入描述】

输入数据第一行是一个整数K（K<100）,代表有K组测试数据。

每组测试数据包含两行：第一行是一个整数N(N<100)，代表有N栋建筑。第二行包含N个不同的整数，每一个对应一栋建筑的高度h(0<h<10000)，

按照建筑的排列顺序给出。

【输出描述】

对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

【样例输入】

3  8  300 207 155 299 298 170 158 65  8  65 158 170 298 299 155 207 300  10  2 1 3 4 5 6 7 8 9 10

【样例输出】

6  6  9

【题目描述】

地面上有一排长度为n的格子1-n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最小得分是多少。

【输入描述】

【样例输入】

3 1 1 1

【样例输出】

-29977

【题目描述】

设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。

例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。

【输入描述】

第一行为n,第二行为用空格隔开的n个整数。

【输出描述】

第一行为输出最大个数max。

第二行为max个整数形成的不下降序列,答案可能不唯一，输出一种就可以了。

【样例输入】

14  13 7 9 16 38 24 37 18 44 19 21 22 63 15

【样例输出】

max=8  7 9 16 18 19 21 22 63

【题目描述】

设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列的长度。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。

例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。

【输入描述】

第一行为n,第二行为用空格隔开的n个整数。

【输出描述】

第一行为输出最大个数max

【样例输入1】

14  13 7 9 16 38 24 37 18 44 19 21 22 63 15

【样例输出1】

max=8

【样例输入2】

7  1 7 3 5 9 4 8

【样例输出2】

max=4

【题目描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间至少有一个空格），计算这套系统最多能拦截多少导弹。

【输入描述】

第1行有1个整数n，代表导弹的数量。（n<=1000）

第2行有n个整数，代表导弹的高度。（雷达给出的高度数据是不大于30000的正整数）

【输出描述】

第一行：最多能拦截的导弹数；

第二行：要拦截所有导弹最少要配备的系统数。

【样例输入】

8  389  207  155  300  299  170  158  65

【样例输出】

6

【题目描述】

小A在生日这天收到了哥哥送来的一盒糖果，这盒糖果共有M个，小A要把这盒糖果放到N个盘子中（允许有盘子不放），请问，有多少种不同的放法？

请注意：数值相同，顺序不同，我们视为是相同的放法，比如，1 1 6，和1 6 1、6 1 1，我们视为是同一种放法。

【输入描述】

输入包含多组测试样例。每组输入的第一行是一个整数t，表示数据有多少组。（t<=10）

接下来t行，每行输入两个整数M和N，代表有糖果的数量和盘子的数量。

（M和N均≥0，且≤20）

【输出描述】

对于每对输入的M和N，输出有多少种放法。

【样例输入】

1  7 3

【样例输出】

8

【题目描述】

地面上有一排长度为n的格子1-n，每个格子上都有一个数xi，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置n+1。取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。

【输入描述】

【输出描述】

【样例输入】

3 1 1 1

【样例输出】

-9993

【题目描述】

求一个数列的所有前缀最小值之和。

即：给出长度为n的数列a[i],求出对于所有1<=i<=n，min(a[1],a[2],...,a[i])的和。

由于读入较大，数列由随机种子生成。

其中a[1]=x，a[i]=(379*a[i-1]+131)%997。

【输入描述】

一行两个正整数n,x，分别表示数列的长度和随机种子。(n<=100000,x<997)

【输出描述】

一行一个正整数表示该数列的前缀最小值之和。

【样例输入】

5 666

【样例输出】

1650

【提示】

数列为{666,304,692,188,596}，前缀最小值为{666,304,304,188,188},和为1650。

前缀最小：

比如，有数列：666 304 692 188 596，前缀最大值为：666,304,304,188,188，和为1650。

对于每个位置的前缀最小值解释如下：对于第1个数666，只有一个数，一定最大；对于第2个数，求出前两个数的最小数，还是304；对于第3个数，求出前3个数的最小数是304……其余位置依次类推，最后求前缀最小值得和。