计蒜客题库

计蒜客题库题解系列:矩形滑雪场

题目测试地址:https://nanti.jisuanke.com/t/203

题目大意:

trs喜欢滑雪。他来到了一个滑雪场,这个滑雪场是一个矩形,为了简便,我们用r行c列的矩阵来表示每块地形。为了得到更快的速度,滑行的路线必须向下倾斜。         例如样例中的那个矩形,可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1,其实25-24-23…3-2-1更长,事实上这是最长的一条。

仔细分析,这题满足 dp 的无后效性,从一个点出发以后是不可能回到这个点的。我们需要按照高度从到到小来转移,这样写起来未免会有些麻烦,代码上不好实现。借助于记忆化搜索的方法可以解决这个问题,记忆化搜索的思想是对于每个状态,只要搜索一次以后,记录下这个状态的最优值,以后在需要用到这个状态就不必要搜索了,因为无后效性,最优永远都不变。


#include 
#include 
#include 
using namespace std;

const int MAXN = 110;

int a[MAXN][MAXN];
int dp[MAXN][MAXN];
int r, c;
int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, 1, -1};

int dfs(int x, int y) {
    if (dp[x][y] != -1) {
        return dp[x][y];
    }
    int ret = 0;
    for (int i = 0;i < 4; ++i) {
        int tx = x + xx[i];
        int ty = y + yy[i];
        if (tx >= 0 && tx < r && ty >= 0 && ty < c && a[tx][ty] < a[x][y]) {
            ret = max(ret, dfs(tx, ty));
        }
    }
    return dp[x][y] = ret + 1;
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0;i < r; ++i) {
        for (int j = 0;j < c; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i = 0;i < r; ++i) {
        for (int j = 0;j < c; ++j) {
            if (dp[i][j] == -1) {
                ans = max(ans, dfs(i, j));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

评论

你的邮箱地址并不会被公开显示 Required fields are marked *

你可以使用 HTML 标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>