【题目描述】

一个旅行者有一个最多能装 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×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

【输入描述】

第一行是一个整数，表示正方形的宽度N (1≤N<100)；

后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。

【输出描述】

至少需要的费用。

【样例输入】

5  1  4  6  8  10  2  5  7  15 17  6  8  9  18 20  10 11 12 19 21  20 23 25 29 33

【样例输出】

109

【题目描写】

N位同学站成一排，音乐老师要请其中的(N−K)位同学出列，使得剩下的KK位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入描述】

输入的第一行是一个整数N（2≤N≤100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130≤Ti≤230）是第i位同学的身高（厘米）。

【输出描述】

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】

8  186 186 150 200 160 130 197 220

【样例输出】

4

【题目描述】

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

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

假设城市中一共有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

【题目描述】

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

【输入描述】

第一行：N (2 <= N <= 1000) 景点数;

第二行：N个整数，每个景点的海拔。

【输出描述】

最多能浏览的景点数。

【样例输入】

8  186 186 150 200 160 130 197 220

【样例输出】

4

【题目描述】Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。【输入描述】第1行，一个整数N(1≤N≤5000)，表示城市数。第2行到第n+1行，每行两个整数，中间用1

【题目描述】

设有N 个正整数（1 <= N <= 50），其中每一个均是大于等于1、小于等于300的数。

从这N个数中任取出若干个数（不能取相邻的数），要求得到一种取法，使得到的和为最大。

例如：当N=5时，有5个数分别为：13，18，28，45，21

此时，有许多种取法，如： 13，28，21 和为62

13, 45 和为58

18，45 和为63

……….



和为63应该是满足要求的一种取法

【输入描述】

第一行是一个整数N

第二行有N个符合条件的整数。

【输出描述】

一个整数，即最大和

【样例输入】

5  13 18 28 45 21

【样例输出】

63

【题目描述】

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

【输入描述】

【样例输入】

3 1 1 1

【样例输出】

-29977

【题目描述】

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

【输入描述】

【输出描述】

【样例输入】

3 1 1 1

【样例输出】

-9993