花生采摘 题解

思路：用邻接矩阵的话找最大值太浪费时间（虽然也能做对），但用点表示更简单，按照每株花生个数排序，排序完再计算时间，最后计算能采摘多少。

AC代码

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int num,x,y,t;
}p[410];
bool cmp(Node a,Node b){
    return a.num>b.num;
}
int m,n,x=0,y,k,t=0,ans=0;
int main(){
    int i,j;
    cin>>m>>n>>k;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++){
            cin>>p[(i-1)*n+j].num;
            p[(i-1)*n+j].x=i;
            p[(i-1)*n+j].y=j;
        }
    sort(p+1,p+(m*n)+1,cmp);//按照花生数量排序
    p[1].t=p[1].x+1;
    for(i=2;i<=m*n&&p[i].num!=0&&p[i-1].t+p[i-1].x<=k;i++)
        p[i].t=p[i-1].t+abs(p[i].x-p[i-1].x)+abs(p[i].y-p[i-1].y)+1;
    for(i-=(p[i-1].t+p[i-1].x>k)?2:1;i>=1;i--)
        ans+=p[i].num;
    cout<<ans;
    return 0;
}