文章

34

粉丝

89

获赞

2

访问

18.5k

头像
滑雪 题解:动态规划+dfs
P1568
发布于2024年3月16日 16:11
阅读数 622

#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int a[105][105];
bool isVisit[105][105];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int n,m;

int dfs(int x,int y){
    if(dp[x][y]) return dp[x][y];
    int maxx = 1;
    for(int i = 0;i < 4;i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] < a[x][y]){
            maxx = max(maxx,dfs(nx,ny)+1);
        }
    }
    dp[x][y] = maxx;
    return maxx;
}

int main(){
    while(cin >> n >> m){
        memset(isVisit,0,sizeof(isVisit));
        memset(dp,0,sizeof(dp));
        int maxx = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j ++){
                cin >> a[i][j];
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j ++){
                dp[i][j] = dfs(i,j);
     ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发