首页分享 3.2 花生采摘

3.2 花生采摘

来源：萌宠菠菠乐园时间：2024-12-01 11:41

来源：NOIP2004普及组 https://ac.nowcoder.com/acm/contest/232/B

鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。

鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”

在这里插入图片描述

我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

从路边跳到最靠近路边（即第一行）的某棵花生植株；

从一棵植株跳到前后左右与之相邻的另一棵植株；

采摘一棵植株下的花生；

从最靠近路边（即第一行）的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。

例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。

输入描述:
输入第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 <= M, N<= 20），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。
接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i,j)下花生的数目，0表示该植株下没有花生。

输出描述:
包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。
示例1
输入

6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1234567

输出

37 1

示例2
输入

6 7 20 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1234567

输出

28 1

题解：一开始看成了DFS，其实不是，就是一道简单的模拟题，因为他的路径是唯一确定的，每次都找剩余的最大的，而最大的又是唯一的，所以模拟一遍就好。

具体过程：
1、先找第一个最大值：若当前时间K减去走到最大值的步数减去采摘时间1，减去返回步数，大于0，就可以继续寻找下一处最大值；若剩余时间K小于零，说明无法返回路边，则第一颗最大花生都采不到，则直接输出0，结束程序。
2、若第一颗没问题则进入else，最大花生数进行累加，时间减掉当前步数减掉采摘时间1，将当前最大花生清零，定义下一个最大花生 r 。
3、进入while死循环，退出条件：
直到当前时间不够采摘下一个最大值时退出；
或者没有花生时退出，结束程序。
while内的具体循环：找最大值 -> 求最大值与上一个最大值的距离d -> 判断（退出）当前花生是否为0，是否时间不够 -> 时间若够，则采花生累加，清零花生，剩余时间更新，上一次的最大值坐标更新

注意：
1、求两点间的距离，横坐标差 + 纵坐标差 d = abs(r.first - t.first) + abs(r.second - t.second);
2、返回去的时间就是当前坐标的横坐标，即垂直路边的垂直距离。
3、要想采摘当前最大值得判断剩余时间是否够采完花生再返回路边

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <queue> #include <sstream> #include <stack> #include <algorithm> using namespace std; typedef long long ll; #define maxn 1000005 #define mod 7654321 #define NIL -1 int arr[30][30]; int M,N,K; int max_num; typedef pair<int,int> PP; PP get_max() { PP r = {0,0};//永远存储最大值的坐标 for(int i = 1;i <= M;i++) for(int j = 1;j <= N;j++) if(arr[r.first][r.second] < arr[i][j]) r = {i,j}; return r; } int main() { cin>>M>>N>>K; for(int i = 1;i <= M;i++) for(int j = 1;j <= N;j++) cin>>arr[i][j]; //存储上一次坐标 PP t = get_max(); //时间判断：过去回来，再加上采摘时间1 //t.first即横坐标，即到路边的垂直距离 if(K < t.first*2 + 1) puts("0"); else { //存储当前最大值 max_num = arr[t.first][t.second]; //采过的都清空为0 arr[t.first][t.second] = 0; //时间减去当前用掉的时间(当前步数+采摘时间1) K -= t.first + 1; while(true) { //存储当前位置坐标 PP r = get_max(); //求相邻两次最大值的距离 int d = abs(r.first - t.first) + abs(r.second - t.second); //若最大值为0,直接结束 if(arr[r.first][r.second] == 0) break; //若当前剩余时间小于(当前步数+采摘1+返回步数),直接结束 if(K < d + 1 + r.first) break; //更新最大花生 max_num += arr[r.first][r.second]; //清空当前最大值 arr[r.first][r.second] = 0; //更新当前剩余时间(减掉当前步数 + 采摘1) K -= d +1; //更新上一次坐标为本次 t = r; } cout<<max_num<<endl; } return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182