90分蒟蒻,#2TLE,佛了,求dalao们康康!

P1434 [SHOI2002] 滑雪

努力变强的cbx @ 2019-09-07 16:22:03

#include <iostream>
#include <algorithm>
using namespace std;
int mp[105][105], n, m, len, ans=1;
bool book[105][105], ed[105][105];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void pro(){
    int i, j;
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            int a, b, c, d, e, f, g, h;
            a = i+dir[0][0]; b = j+dir[0][1];
            c = i+dir[1][0]; d = j+dir[1][1];
            e = i+dir[2][0]; f = j+dir[2][1];
            g = i+dir[3][0]; h = j+dir[3][1];
            if(a>=0&&a<n&&b>=0&&b<m){
                if(mp[i][j]>mp[a][b]){
                    ed[i][j] = true;
                }
            }
            if(c>=0&&c<n&&d>=0&&d<m){
                if(mp[i][j]>mp[c][d]){
                    ed[i][j] = true;
                }
            }
            if(e>=0&&e<n&&f>=0&&f<m){
                if(mp[i][j]>mp[e][f]){
                    ed[i][j] = true;
                }

            }if(g>=0&&g<n&&h>=0&&h<m){
                if(mp[i][j]>mp[g][h]){
                    ed[i][j] = true;
                }
            }
        }
    }
}

void dfs(int x, int y, int l){
    int i;
    if(ed[x][y]==false){
        len = max(l, len);
        return;
    }
    for(i = 0; i < 4; i++){
        int dx = x+dir[i][0];
        int dy = y+dir[i][1];
        if(dx<0||dx>=n||dy<0||dy>=m||book[dx][dy]){
            continue;
        }
        if(mp[x][y]>mp[dx][dy]){
            book[dx][dy] = true;
            dfs(dx, dy,l+1);
            book[dx][dy] = false;
        }
    }
    return;
}

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            scanf("%d", &mp[i][j]);
        }
    }
    pro();//预处理,找出那些“尽头”
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            if(ed[i][j]){
                fill(book[0], book[0]+105*105, false);
                book[i][j] = true;
                dfs(i, j, 1);
                ans = max(len, ans);
                len = 0;
            }
        }
    }
    printf("%d", ans);
}

by Nelson_Wang @ 2019-09-07 16:29:53

这题不是记忆化搜索吗?


by 努力变强的cbx @ 2019-09-07 16:41:05

@Nelson_Wang 好,多谢dalao,我以为暴力出奇迹(其实是不会记忆化搜索)(大雾)


by junyu33 @ 2019-09-19 17:34:18

剪枝909ms


by cpphzj @ 2019-11-10 14:59:09

if (l[x][y]) return l[x][y];

这个很重要。


|