OpenJ_Bailian - 1088 滑雪（记忆化搜索）

题意：给定一个二维数组，一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，输出可以滑行的最长区域的长度。

分析：对于每一个点，进行记忆化搜索。若某点可以向四周某几个点滑行，记忆化搜索求出这几个可滑行点的最长滑行长度，取最大值，则该点的最长滑行长度为最大值+1.

注意：不能直接dp[x][y]=max(dp[x][y],dfs(tmpx,tmpy)+1)，因为若四周没有可滑行的点，则该点最长滑行长度dp[x][y]会输出0，而实际dp[x][y]为1，分析中的方法可避免这个问题。

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN = 100 + 10;

int pic[MAXN][MAXN];

int dp[MAXN][MAXN];

const int dr[] = {0, 0, 1, -1};

const int dc[] = {1, -1, 0, 0};

int R, C;

bool judge(int x, int y){

    return x >= 0 && x < R && y >= 0 && y <= R;

}

int dfs(int x, int y){

    if(dp[x][y]) return dp[x][y];

    int ans = 0;

    for(int i = 0; i < 4; ++i){

        int tmpx = x + dr[i];

        int tmpy = y + dc[i];

        if(judge(tmpx, tmpy) && pic[tmpx][tmpy] < pic[x][y]){

            ans = max(ans, dfs(tmpx, tmpy));

        }

    }

    return dp[x][y] = ans + 1;

}

int main(){

    scanf("%d%d", &R, &C);

    for(int i = 0; i < R; ++i){

        for(int j = 0; j < C; ++j){

            scanf("%d", &pic[i][j]);

        }

    }

    int ans = 0;

    for(int i = 0; i < R; ++i){

        for(int j = 0; j < C; ++j){

            ans = max(ans, dfs(i, j));

        }

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

OpenJ_Bailian - 1088 滑雪（记忆化搜索）

最新文章

热门文章