题目描述

为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找 出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”

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

1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？

注意 可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。

样例

输入

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

输出

37

首先要明白这个题的寻找花生是一个固定的路径（原因：每一个花生不一样，并且依次采摘最大的花生数）
直接模拟，以时间为限制，不断的对采摘花生的个数进行判断。
注意采摘花生的时候也需要时间+1；

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=25;
int n,m,k;
int w[N][N];

PII get_max()   //找寻最大值
{
    PII r={0,0};
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        if(w[i][j]>w[r.x][r.y])
        r={i,j};
    return r;
}

int main()
{
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
          cin>>w[i][j];

    auto t=get_max();  //最大值
    if(t.x*2+1>k)  puts("0");//判断是否超出time
    else   //没有超出
    {
        int res=0;    //花生数
        res+=w[t.x][t.y];   //加入
        w[t.x][t.y]=0;  //并使它等于0，便于寻找下一个最大值
        k-=t.x+1;  //采完这个花生之后的剩余时间

        while(true)
        {
            auto r=get_max();   //下一个最大值
            if(w[r.x][r.y]==0)  break;    //为找到最后一个花生。
            int time=abs(r.x-t.x)+abs(r.y-t.y)+1;  //下一个花生到上一个花生需要的time
            if(time+r.x>k)  break;   //超时，break

            res+=w[r.x][r.y];   //不超时，加入
            w[r.x][r.y]=0;  //置0
            k-=time;      //
            t=r;    //使这个花生成为上一个花生
        }
        cout<<res<<endl;
    }
    return 0;
}