一道dfs和dp结合的好题 --- Longest Run on a SnowboardUVA-10285

心已赠人 2021-09-29 18:18 181阅读 0赞

题目链接：

[https://vjudge.net/problem/19213/origin][https_vjudge.net_problem_19213_origin]

大致题意：

一个滑雪者想知道自己在固定高度的山坡中最多能滑的距离是多少。

思路：

首先想到的就是dfs，但是。。超时了，所以我们要用到动态规划进行优化。

dfs的思路就是从第一个位置开始dfs搜索。

dp的思路就是数形的思维，每一个树的根节点就是dp\[x\]\[y\]。这是一个4叉树，当dp\[x1\]\[y1\] < dp\[x\]\[y\]的时候进行向下递归，每次操作加上权值1，这个操作最终会返回一个最大值。

下面是AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <string.h>
    
    using namespace std;
    const int MX = 100+10;
    int vis[MX][MX]; //vis数组记忆化搜索，防止重复。但是在这道题貌似不需要。。。
    int dp[MX][MX], mp[MX][MX];
    int n, m, ans;
    string name;
    int xx[] = {
         1, 0, -1, 0};
    int yy[] = {
         0, 1, 0, -1}; //四个方向
    
    
    int dfs(int x, int y)
    {
        if(vis[x][y]) return dp[x][y];
        for(int i = 0; i < 4; ++i)
        {
            int x1 = x+xx[i];
            int y1 = y+yy[i];
            if(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && mp[x1][y1] < mp[x][y]) //注意递归边界
            {
                dp[x][y] = max(dfs(x1, y1)+1, dp[x][y]); //选权值最大的边
            }
        }
        vis[x][y] = 1; //记忆化搜索优化
        return dp[x][y];
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while(T--)
        {
            ans = 0;
            name.clear();
            memset(vis, 0, sizeof(vis));
            memset(dp, 0, sizeof(dp));
            memset(mp, 0, sizeof(mp));
            cin >> name;
            scanf("%d %d", &n, &m);
    
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= m; ++j)
                    scanf("%d", &mp[i][j]); //初始化mp数组
    
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= m; ++j)
                {
                    int h = dfs(i, j);
                    ans = max(ans, h);
                }
            cout << name << ": " << ans+1 << endl; //起始点也算
        }
    }

如有疑问，欢迎评论指出！

转载于:https://www.cnblogs.com/mpeter/p/10355792.html

[https_vjudge.net_problem_19213_origin]: https://vjudge.net/problem/19213/origin
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/74d033095f054cf280e80275a137ae65.png