P1086 花生采摘

题目描述

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

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

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

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

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

3. 采摘一棵植株下的花生；

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

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

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

输入格式

第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M×N（1≤M,N≤20），多多采花生的限定时间为K（0≤K≤1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i+1行的第j个整数P（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

输出 #1复制

37

输入 #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

输出 #2复制

28

说明/提示

NOIP2004普及组第2题

分析：

这道题目非常有趣，要做出它不难，但要从数学的角度完整地分析它，确实需要一定的数学功底。

要点：

1.我们先将每一个点的植株坐标化，横纵坐标都从\(1\)开始。

2.这是一个网格图，而多多只能沿着网格的线移动，那么从一株花生采摘点到下一株花生采摘点最少需要花费的时间是两株花生的\(abs(横坐标1-横坐标2)+abs(纵坐标1-纵坐标2)\)

3.我们在计算消耗时间时，起点应该从横坐标与\(MAX\)植株的横坐标相同的点开始。

4.这一点是解题关键：在采摘花生的过程中，我们该怎么判断这一个点就是我们能到达的最后一个采摘点？

思考一下，我们在采摘完这一个花生后，要去采摘下一个花生，时间会怎么消耗。

就是说，我们在采摘完这一株后，去往下一株，然后再回去比采完这一株就直接回去花费的时间至少多一个单位时间(采摘花的时间)，那么如果这一株采完了发现直接跳回去时间不够了，那这一株就不采，退回前一株，然后直接退回去。而且，这样判断，是最完整的。（证明的思考，就留给大家啦!)

下面，我们就用数学的思想证明：

两采摘点的最少花费时间是\(abs(x~1~-x~2~)+abs(y~1~-y~2~)\)。

设j是下一个采摘点，i是当前的。
\[ abs(x[i]-x[i+1])+abs(y[i]-y[i+1])+abs(x[i+1]-x[i+2])+\\abs(y[i+1]-y[i+2])+...+abs(x[j-1]-x[j])+abs(y[j-1]-y[j])\\>=abs(x[i]-x[i+1])+abs(x[i+1]-x[i+2])+...+abs(x[j-1]-x[j])\\>=(x[i]-x[i+1])+x[i+1]-x[i+2])+...+(x[j-1]-x[j])\\>=x[i] \]

代码实现：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 400+3;
struct point{
    int x,y,value;//y是横坐标，x才是纵坐标
};
point p[MAXN];//因为在网格上没有什么操作会要保留二维数组的结构，用一维数组一个一个点存就行了
bool cmp (point x,point y){
    return x.value>y.value;
}
using namespace std;
int main(){
    int n,m,k,t=0,ans=0;
    scanf("%d%d%d",&m,&n,&k);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j){
        p[++t]=(point){i,j,0};
        scanf("%d",&p[t].value);
    }
    sort(&p[1],&p[m*n+1],cmp);//依照价值排序，首先采价值最大的
    p[0].x=0;p[0].y=p[1].y;//要点3
    for(int i=1;i<=n*m;++i){
        k-=abs(p[i-1].x-p[i].x)+abs(p[i-1].y-p[i].y)+1;
        if(k<p[i].x) break;ans+=p[i].value;//要点4
    }
    printf("%d",ans);
    return 0;
}

本人文笔不好，请谅解，谢谢 QwQ !

P1086 花生采摘

原文：https://www.cnblogs.com/majorin/p/11997914.html