bfs RE。。。 dfs TLE。。。必须用DP吗

RT

2 条评论

  • @ 2018-02-11 20:05:16

    要用记忆化搜索。
    我们每一次搜寻到的地点算出来的指都是一样的。
    不需要重新算了。
    int n,m;
    int a[555][555];
    int dp[555][555];
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    inline int dfs(int x,int y){
    if(dp[x][y]) return dp[x][y];
    int rt=0,tx,ty;
    for(int i=0;i<4;i++){
    tx=x+dx[i];
    ty=y+dy[i];
    if(tx<0||ty<0||tx==n||ty==m) continue;
    if(a[x][y]>a[tx][ty]) rt=max(rt,dfs(tx,ty));
    }
    rt++;
    dp[x][y]=rt;
    return rt;
    }

  • @ 2016-12-01 23:40:24

    记忆化搜索。
    可以发现,如果我们是从高到低搜索,那么对于任意一个高度,只需要考虑所有比他高度低的点就可以了。
    那么,我们可以在搜索的过程中,对每个位置都记录【从当前位置出发,最长能够走的距离】,即可将时间复杂度降低到O(NM),与输入复杂度一致。
    特别提醒,可能有N不等于M的情况,以及高度相同并且相邻的情况。

  • 1

信息

ID
1011
难度
6
分类
动态规划 点击显示
标签
递交数
8799
已通过
2552
通过率
29%
上传者