洛谷 P1086 花生采摘

嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P1086

 

这道题首先主要的思想就是贪心：

每次寻找花生田中价值最大的花生，然后通过一种类似dfs的方法来判断这株花生能否摘。

如果不能摘，则return；如果能摘，则ans+，且将时间扣除。

 

注意：

1.这个题的细节比较多，尤其是在是否能摘花生时关于时间的细节比较多。其余细节在代码中已解释。

2.弄清横纵坐标问题，x在这里表示行，y表示列。

 

AC代码：

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

using namespace std;

int g[21][21], n, m, k, ans;

inline void dfs(int t, int x, int y){
    int maxx, maxy, maxn = -1;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(g[i][j] > maxn){
                maxn = g[i][j];
                maxx = i;
                maxy = j;
            }
        }
    }
    if(!y) y = maxy;//如果在路边，跳到maxy
    if(t < abs(x - maxx) + abs(y - maxy) + maxx + 1 || !g[maxx][maxy]) return;
    //若时间<采(Maxx,Maxy)的时间+回到路边的时间或是(Maxx,Maxy)上没有花生,就结束
    //注意+1，回到路边还需要1单位时间 
    else{
        ans += g[maxx][maxy];
        g[maxx][maxy] = 0;
        dfs(t - abs(x - maxx) - abs(y - maxy) - 1, maxx, maxy);//继续 
    }//采摘 
}

int main(){
    scanf("%d%d%d", &m, &n, &k);
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &g[i][j]);
        }
    }
    dfs(k, 0, 0);
    printf("%d\n", ans);
    return 0;
}