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。

相关问题

p1046 [noip2005 普及组] 陶陶摘苹果

### 回答1：
题目描述：

陶陶去苹果园摘苹果，这个苹果园很特别，他的苹果树排成了一个矩形网格（如下图）。

其中红色数字代表了对应的苹果数目。陶陶可以沿着网格线爬上爬下去摘苹果，但不能斜着走或越过两棵苹果树之间的空地。陶陶想要摘到尽量多的苹果，他应该怎么摘？

输入输出格式：

输入格式：

输入的第一行有两个整数n,m（1<=n,m<=10）表示苹果园的大小。接下来n行，每行m个整数，用空格隔开，表示每棵树上的苹果数目a（<=a<=100）。

输出格式：

输出一个整数，表示陶陶能摘到的最多的苹果数。

输入输出样例：

输入样例#1：

3 4
1 2 3 4
5
1 3

输出样例#1：

13

输入样例#2：

3 3
1 2 3
5
1 3

输出样例#2：

11

算法1

(暴力枚举) $O(n^2)$

我们可以枚举陶陶的起点，然后从起点开始，每次向右或向下走一步，直到到达右下角。在这个过程中，我们可以记录下经过的苹果数，最后取所有路径中经过的苹果数的最大值即可。

时间复杂度

枚举起点的时间复杂度是 $O(n^2)$，对于每个起点，我们需要走 $O(n)$ 步，因此总时间复杂度是 $O(n^3)$。

C++ 代码

算法2

(动态规划) $O(n^2)$

我们可以用 $f(i,j)$ 表示从 $(1,1)$ 到 $(i,j)$ 的最大苹果数。那么 $f(i,j)$ 可以从 $f(i-1,j)$ 和 $f(i,j-1)$ 转移而来，即：

$$ f(i,j)=\max\{f(i-1,j),f(i,j-1)\}+a(i,j) $$

其中 $a(i,j)$ 表示 $(i,j)$ 这个位置的苹果数。

时间复杂度

我们需要计算 $O(n^2)$ 个状态，每个状态需要 $O(1)$ 的时间计算，因此总时间复杂度是 $O(n^2)$。

C++ 代码

### 回答2：
这道题目是一道经典的搜索题目，需要对搜索算法有所了解才能够解决。

题意概括如下：有一棵苹果树，树上有许多苹果，可以在树上选择一个点作为起点，向下摘苹果，因为树的形状不同，所以每次摘苹果的时候只能摘取横坐标在当前点横坐标之后，且纵坐标比当前点大的苹果。一旦摘了一个苹果之后，这个点就成为了新的起点，并且可以继续向下摘苹果，主人公摘苹果的速度越快，所用时间也越短。请问主人公最短需要多长时间才能摘完所有苹果？

解题思路如下：首先，我们需要先对树进行处理。处理时对每个横坐标按照从小到大的顺序进行排序，如果横坐标相同则按照纵坐标从大到小的顺序进行排序。这样处理之后，如果主人公从一个点出发摘了一个苹果，那么他下一次摘取苹果的起点只能是横坐标在当前点横坐标之后且纵坐标比当前点大的苹果。因为对于同一横坐标的苹果，纵坐标从大到小排列，所以从当前点开始，每个点到达的下一个点都是唯一的，不会有多余的决策。

接下来使用dfs算法进行搜索，搜索的过程中维护当前所在位置和当前时间。每次到达新的点，将时间加上到达该点所需的时间，并将当前位置更新为到达的新点，并进入下一层搜索。当所有的苹果被摘取的时候，将当前时间和历史最短时间进行比较，取最小值。

需要注意的是，在搜索过程中，如果不加任何剪枝，时间复杂度会非常高，甚至无法通过测试。因此需要使用一些剪枝技巧。比如，如果当前时间已经大于历史最短时间，则直接返回，不再进行搜索；对于当前点可以到达的下一层节点，如果剩余的所有苹果的总数已经小于历史最短时间，也可以直接返回。这些剪枝技巧可以大幅降低搜索的时间复杂度。

最终，完成搜索后，输出历史最短时间即可。

### 回答3：
这道题是一道模拟题，需要模拟陶陶摘苹果的过程。首先输入陶陶的身高和苹果树的高度，然后输入每个苹果离地面的高度。我们可以用一个循环来遍历每个苹果的高度，判断这个苹果是否可以被陶陶摘取。如果这个苹果的高度和陶陶的身高之和大于苹果树的高度，那么这个苹果就可以被陶陶摘取。最后，输出陶陶可以摘取的苹果的数量。

具体的实现过程如下：

1. 输入陶陶的身高和苹果树的高度。

2. 定义一个计数变量，记录陶陶可以摘取的苹果数量。

3. 用循环遍历每个苹果的高度：

（1） 输入这个苹果离地面的高度。

（2） 判断这个苹果是否可以被陶陶摘取：如果这个苹果的高度和陶陶的身高之和大于苹果树的高度，那么这个苹果就可以被陶陶摘取。

（3） 如果可以被摘取，就把计数变量加一。

4. 输出陶陶可以摘取的苹果数量。

完整的代码如下：

#include <iostream>

using namespace std;

int main() {
    int n, m, h; // n: 苹果个数，m: 苹果树的高度，h: 陶陶的身高
    int count = 0; // 计数器
    cin >> n >> m >> h;

    for (int i = 0; i < n; i++) {
        int a; // 苹果离地面的高度
        cin >> a;
        if (h + a >= m) { // 如果苹果可以被摘取
            count++;
        }
    }

    cout << count << endl; // 输出陶陶可以摘取的苹果数量

    return 0;
}

需要注意的地方是，本题的数据规模很小，因此可以使用 int 类型进行计算和存储，不会发生数据溢出的问题。

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

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

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