找出NOIP改进小组不同算法对应的练习。

问题描述:

迈克尔喜欢滑雪并不奇怪，因为滑雪确实令人兴奋。但是为了获得速度，滑行区域必须是向下倾斜的，当你滑行到坡底的时候，你不得不再次上坡或者等电梯来接你。迈克尔想知道一个地区持续时间最长的滑坡。该区域由二维数组给出。数组中的每个数字代表该点的高度。这里有一个例子:

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某一点滑到四个相邻点中的一个，上下左右，当且仅当高度降低。在上面的例子中，一个滑动滑坡是24-17-16-1。当然25-24-23-...-3-2-1更长。其实这是最长的一个。

输入格式:

第一行表示行数r和列数c (1

输出格式:

只有一个整数表示最长区域的长度。

样本输入样本输出

5 5 25

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

如果想买几个值的珍珠，必须额外支付10的珍珠，如果买1的珍珠，必须支付110。一颗珍珠可以装更贵的珍珠，所以用贵的买各种珍珠可能比买便宜的更省钱。比如买价值2的100件，价值1的1件。这时候买101件，价值2，是比较好的方案。输入几种珍珠要买，问在能装满高价珍珠的条件下至少要多少钱。

陶陶摘了苹果。

问题描述

陶陶的院子里有一棵苹果树。每年秋天，树上都会有n个苹果。当苹果成熟时，陶陶会跑去摘苹果。陶陶有一条长凳。当她不能直接用手摘苹果时，她会踩在板凳上再试一次。

现在我们知道了n个苹果离地的高度，以及陶陶手伸直时能达到的最大高度，h cm。请帮助陶陶计算一下，如果她想摘30%的苹果，她的长凳应该是多少厘米。假设她碰了一个苹果，它会掉下来。

输入格式

第一行是两个正整数N和H，分别代表苹果的数量和陶陶把手伸直时能达到的最大高度(以厘米为单位)。第二行是用空格隔开的n个正整数ai，分别代表n个苹果的高度(以厘米为单位)。

数据范围

N≤1000且n是10的倍数，h≤140，100≤ai≤220。

输出格式

只有一个整数表示凳子的最小高度(厘米)。如果她不用板凳也能完成任务，输出0。

投入产出样本

样本输入样本输出

10 140

151 172 183 175 164 178 182 178 192 148 24

纪念邮票

问题描述

邮局最近发行了一套纪念邮票。有N套不同面额的邮票，按编号顺序是1，2，…，N。肖航是一名集邮者。他非常喜欢这套邮票。可惜他现在身上只有M分，不够买所有的邮票。他想买的越多越好，最好把刚才的钱都花完。作为一名集邮者，肖航不想买号码断断续续的邮票。因此，肖航打算购买面值从A到B的b-a+1连号邮票，总价值正好是m

你的任务是找出所有符合要求的方案，以便

[15,15]

矩形分割(切割)

问题描述

由于某些需要，我们不得不将一块N×M的木板切割成1×1的小方块。

对于一个板材，我们只能从某一条水平线或者某一条垂直线(在网格线上)切割，板材凹凸不平，所以从不同的线上切割需要花费不同的价格。而且对于一块板来说，切割一次后就分成两块，不能把两块板放在一起再跨板切割成四块，只能再切割两块。

现在，给出不同线切割的成本，求将整块板分成1x1个小方块的最小成本。

输入格式

输入文件的第一行包括n和m，表示一个长n宽m的矩阵。

第二行包括N-1个非负整数，分别代表沿N-1条横线切割的代价。

第二行包括M-1个非负整数，分别代表沿M-1条垂直线切割的代价。

数据范围

对于60%的数据，有1 ≤ N，m≤100；对于100%的数据，有1 ≤ N，m ≤ 2000。

输出格式

输出表示最小成本的整数。

投入产出样本

样本输入样本输出

2 2

三

3 9

盒子(盒子)

问题描述

n个盒子排成一行(1

输入格式

一行，n，a，b，用空格隔开。

输出格式

一行，输出布局方案总数。

投入产出样本

样本输入样本输出

2 1 1 9