p1048 [noip2005 普及组] 采药

题目描述

有一个草药园，里面有很多草药，采每一株草药都有一个时间ti和一个价值vi。现在有一个采药人，他要在规定时间内采到总价值最大的草药。采药人采药的速度是一定的，他可以选择任意多株草药采摘。这个草药园有点神秘，同一株草药不能采摘两次，而且采摘草药的时间不能超过规定时间。现在给你草药园中每株草药的采摘时间和价值，请你编一个程序输出采到的草药的最大总价值。

输入输出格式

输入格式：

第一行有两个整数T（1<=T<=100）和M（1<=M<=100）。

接下来的M行每行包括两个在1到100之间的整数，分别表示采摘这株草药的时间和这株草药的价值。

输出格式：

只有一个整数，即采到的草药的最大总价值。

输入输出样例

输入样例#1：

70 3
71 100
69 1
1 2

输出样例#1：

3

输入样例#2：

20 5
5 10
10 10
6 12
8 13
7 11

输出样例#2：

36

说明

在样例#1中，采药人有70个时间单位的时间，他可以选择采第2株和第3株草药，总价值为1+2=3。

在样例#2中，采药人有20个时间单位的时间，他可以选择采第1株、第3株和第4株草药，总价值为10+12+13=35。

相关问题

P1047 校门外的树 Noip2005普及组第二题

P1047 校门外的树 是一道IT类问题，这是一道简单的模拟题，题目描述如下：

给定了一段道路的长度和一些树的位置，要求计算出这段道路上没有被树覆盖的长度。具体做法是先将树的位置记录在一个数组中，然后对数组进行排序，从而得到每两棵相邻树之间的空隙长度，将这些空隙长度累加起来即可得到未被覆盖的长度。如果第一棵树的位置不是0，则需要在0和第一棵树之间再计算一段长度。

p1044 [noip2003 普及组] 栈

题目描述：

给定一个长度为n的序列a1,a2,...,an，你需要使用一个栈进行排序。排序的规则为：

每次弹出一个或多个元素，这些元素都是未出栈的元素中的最小值。
按照弹出的顺序将元素输出。
例如，如果输入序列为3 1 2，则有以下两种排序方式：

先弹出元素1，再弹出元素2，最后弹出元素3，得到排序序列1 2 3；
先弹出元素2和1，再弹出元素3，得到排序序列2 1 3。
输入格式
第一行包含一个整数n。

第二行包含n个整数，表示序列a。

输出格式
输出一个序列，表示通过栈排序得到的序列。

输入样例1：
5
5 4 3 2 1
输出样例1：
1 2 3 4 5

输入样例2：
5
5 4 3 2 1
输出样例2：
1 2 3 4 5

提示
数据范围
1≤n≤1000
数据范围的原因是栈的深度不能太深，否则会栈溢出，导致程序崩溃。