TLE求优化90pts

P1434 [SHOI2002] 滑雪

mo_mo_yu0_0 @ 2024-10-10 22:15:57

加了快递没有过,T了#2 code


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, a[110][110], vis[110][110], ans;
int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
ll dfs(ll x, ll y, ll d) {
    ll s = -1;
    if (a[x - 1][y] < a[x][y]) {
        vis[x - 1][y] = dfs(x - 1, y, d + 1);
        s = max(s, vis[x - 1][y]);
    }
    if (a[x + 1][y] < a[x][y]) {
        vis[x + 1][y] = dfs(x + 1, y, d + 1);
        s = max(s, vis[x + 1][y]);
    }
    if (a[x][y - 1] < a[x][y]) {
        vis[x][y - 1] = dfs(x, y - 1, d + 1);
        s = max(s, vis[x][y - 1]);
    }
    if (a[x][y + 1] < a[x][y]) {
        vis[x][y + 1] = dfs(x, y + 1, d + 1);
        s = max(s, vis[x][y + 1]);
    }
    if (s == -1)return d;
    return s;
}
int main() {
    n=read();
    m=read();
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++) {
            a[i][j] = 10000000000;
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            a[i][j]=read();
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!vis[i][j])vis[i][j] = dfs(i, j, 1);
            ans = max(ans, vis[i][j]);
        }
    }
    cout << ans;
}

by MLE_Automaton @ 2024-10-10 22:21:16

@mo_mo_yu0_0 有没有一种可能,这题要用dp或记搜。


by mo_mo_yu0_0 @ 2024-10-10 22:27:13

@ChenXiJie2013 我写的vis记搜呀


|