洛谷[SHOI2002]滑雪题解

什么破题啊

简直就是浪费我时间！

我每天还被我xf定目标了不知道嘛！

朴素的搜索只能得90分

#include <cstdio>

#include <iostream>

using namespace std;

const int N = ;

bool vis[N][N];

int n, m, mp[N][N], ans;

int dx[] = {-, , , }, dy[] = {, , -, };

int read() {

    int s = , w = ;

    char ch = getchar();

    while(!isdigit(ch)) {if(ch == '-') w = -; ch = getchar();}

    while(isdigit(ch)) {s = s *  + ch - ''; ch = getchar();}

    return s * w;

}

void dfs(int xx, int yy, int sum) {

    ans = max(ans, sum);

    for(int i = ; i < ; i++) {

        int x = dx[i] + xx, y = dy[i] + yy;

        if(x >=  && x <= n && y >=  && y <= m && !vis[x][y] && mp[x][y] < mp[xx][yy])

            dfs(x, y, sum + );

    }

}

int main() {

    n = read(), m = read();

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            mp[i][j] = read();

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            dfs(i, j, );

    printf("%d\n", ans + );

    return ;

}

需要加入记忆化搜索

真想骂街我的记忆化怎么怎么就不对

可能是我太毛躁了

于是我就点开了题解

Code：

#include <cstdio>

#include <iostream>

using namespace std;

const int N = ;

int n, m, mp[N][N], ans, maxn[N][N];

int dx[] = {-, , , }, dy[] = {, , -, };

int read() {

    int s = , w = ;

    char ch = getchar();

    while(!isdigit(ch)) {if(ch == '-') w = -; ch = getchar();}

    while(isdigit(ch)) {s = s *  + ch - ''; ch = getchar();}

    return s * w;

}

int dfs(int xx, int yy) {

    if(maxn[xx][yy] != ) return maxn[xx][yy];

    int anss = ;

    for(int i = ; i < ; i++) {

        int x = dx[i] + xx, y = dy[i] + yy;

        if(x >=  && x <= n && y >=  && y <= m && mp[x][y] < mp[xx][yy])

            anss = max(anss, dfs(x, y) + );

        maxn[xx][yy] = max(maxn[xx][yy], anss);

    }

    return maxn[xx][yy];

}

int main() {

    n = read(), m = read();

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            mp[i][j] = read(), maxn[i][j] = ;

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++) {

            int anss = dfs(i, j);

            ans = max(ans, anss);

        }

    printf("%d ", ans);

    return ;

}

TTT，TnmT！不是脏话

谢谢收看，祝身体健康！（反正我是被气死了）

巴特西

洛谷[SHOI2002]滑雪题解

最新文章

热门文章