【违规紫衫】有大佬吗？

Leo2020 @ 2021-07-24 22:40:30

#include<bits/stdc++.h>
using namespace std;
const int XY[5]={1,0,-1,0,1};
int n,m,num[1015][1015],ans;
void dfs(int x,int y,int s,int t){
    for(int i=0;i<5;i++){
        int X=x+XY[i],Y=y+XY[i+1];
        if(0<=X<n&&0<=Y<m&&num[X][Y]<s){
            dfs(X,Y,num[X][Y],t+1);
        }
    }
    ans=max(ans,t);
}
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> num[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dfs(i,j,num[i][j],0);
        }
    }
    cout << ans << endl;
    return 0;
}

by Leo2020 @ 2021-07-24 23:13:40

@BlankAo 谢谢

by wsyhb @ 2021-07-24 23:21:44

@Leo2020

事先说好，我不是大佬。

不能直接纯搜索，因为路径条数是指数级的，会 TLE。

有关路径条数是指数级的，举个例子：

16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

说明：从任意一个点出发，（只要不出边界）既可以向下走，也可以向右走。那么从左上角出发，走 6 步到右下角，其中 3 步向右，3 步向下，不同方向的走法可以任意排列。

（正解后面接着说）

by wsyhb @ 2021-07-24 23:29:13

@Leo2020

然后可以记忆化搜索，不过我想简单讲一讲排序的做法，个人认为更简单。

把这些点的位置编个号，然后把它们按高度从大到小排序（可以直接写比较函数，也可以用结构体）。

记 c_{i,j} 表示从高处滑到 (i,j) 最多可以滑多远。由于只会从高处滑到低处，那么按这样的顺序，完全可以利用已知信息计算 c。也就是枚举 (i,j) 相邻的格子 (x,y)，若 h_{x,y}>h_{i,j}，令 c[i][j]=max(c[i][j],c[x][y]+1) 即可。（当然 c 初始值为 1）

最后输出 c 数组最大值即可。

by Loser_King @ 2021-07-24 23:34:37

每次dfs结束要开一个数组来记录当前点上的最长路径，如f[i][j]=max(f[i][j],t)，然后在dfs开头加一句if(f[i][j]){t=f[i][j];return;}

（我的做法是带返回值的dfs，和你的略有不同。所以以上仅供参考，真的不明白可以看题解）

by 一念之间、、 @ 2021-07-24 23:52:37

@wsyhb 您是神仙

by wsyhb @ 2021-07-25 11:29:56

@ー念之间、、 ？

原来我是您的小号啊，那没事了~

by 一念之间、、 @ 2021-07-25 23:51:13

@wsyhb 不，这不是我小号，只不过是路过看见您来膜一膜罢了