[NOIP2004]花生采摘

NOIP 2004 普及组 花生采摘 题解

原题链接

题目分析

看到题目中的采摘情景，不难想到这道题我们应该使用搜索来进行处理。题目中要求每次都采摘剩下花生中果实数最大的一棵植株，所以考虑使用DFS进行处理。

易错点分析

采摘策略问题

你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。

这一段表明了我们的采摘策略：每次都采摘剩下的最多的那一堆，如果没有仔细看这段话，就可能会把这道题理解成另一道题，也就是如何采摘使得采摘数最多。

跳跃方式问题
题目中并没有说在路上走需要花时间，所以第一步我们一定要直接取直线距离进入田里，不然时间会大幅增加

核心代码

void DFS(int sum, int x, int y) {//sum表示还有多少时间的剩余，x和y表示当前位置的坐标int maxx, maxy, maxnum = -999;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (a[i][j] > maxnum) maxx = i, maxy = j, maxnum = a[i][j];}}//寻找当前的最小值if (y == 0) y = maxy;//从路边走直线到第一站if (sum < abs(x - maxx) + abs(y - maxy) + maxx + 1 || a[maxx][maxy] == 0) {return;} else {ans += a[maxx][maxy], a[maxx][maxy] = 0; //已经摘完了DFS(sum - abs(x - maxx) - abs(y - maxy) - 1, maxx, maxy);} }

完整代码

#include<bits/stdc++.h> const int MAXN = 25; using namespace std; int m, n, k; int a[MAXN][MAXN]; int ans; void DFS(int sum, int x, int y) {//sum表示还有多少时间的剩余，x和y表示当前位置的坐标int maxx, maxy, maxnum = -999;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (a[i][j] > maxnum) maxx = i, maxy = j, maxnum = a[i][j];}}//寻找当前的最小值if (y == 0) y = maxy;//从路边走直线到第一站if (sum < abs(x - maxx) + abs(y - maxy) + maxx + 1 || a[maxx][maxy] == 0) {return;} else {ans += a[maxx][maxy], a[maxx][maxy] = 0; //已经摘完了DFS(sum - abs(x - maxx) - abs(y - maxy) - 1, maxx, maxy);} } int main() { //freopen(".in", "r", stdin); //freopen(".out", "w", stdout);ios::sync_with_stdio(false);cin >> m >> n >> k;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j];}}DFS(k, 0, 0);cout << ans;return 0; }

运行结果