记忆化搜索TLE一个点求助DaLaos

Clay_L @ 2023-01-31 11:24:28

#include<bits/stdc++.h>
using namespace std;
int n,m,a[111][111],f[111][111],ans;
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};
int dfsp(int x,int y)
{
    int t=f[x][y],xx,yy;
    if(t!=-1) return t;
    t=1;
    for(int i=0;i<4;i++)
    {
        xx=x+dx[i],yy=y+dy[i];
        if((xx<1||xx>n||yy<1||yy>m)||a[x][y]<=a[xx][yy]) continue;
        t=max(t,dfsp(xx,yy)+1);
    }
    return t;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j],f[i][j]=-1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(ans,dfsp(i,j));
    cout<<ans<<endl;
    return 0;
}

by ttltony @ 2023-01-31 11:29:06

@TechnobladePlus 你这dfsp改一下行不行！！！！！！！！！！！！！

你把这改成dp就行了啊，或者用bfs试试，不要随便在讨论区提问，除非是迫不得已的时候，自己上网查一下，也可以看看我的代码啊

我的代码:

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n, m;
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
int shuru[101][101];
int dp[101][101];

struct node {
    int x;
    int y;
    int h;
} a[10001];

bool Com(node n1, node n2) {
    return n1.h < n2.h;
}

int main() {
    int res = 0;
    cin >> n >> m;
    int k = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ ) {
            a[k].x = i;
            a[k].y = j;
            cin >> a[k].h;
            shuru[i][j] = a[k].h;
            k ++ ;
        }
    sort(a, a + n * m, Com);
    for (int i = 0; i < n * m; i ++ ) {
        for (int j = 0; j < 4; j ++ ) {
            int f = dx[j] + a[i].x, s = dy[j] + a[i].y;
            if (f >= 0 && f < n && s >= 0 && s < m && a[i].h > shuru[f][s]) dp[a[i].x][a[i].y] = max(dp[a[i].x][a[i].y], dp[f][s]+1);
        }
        res = max(res, dp[a[i].x][a[i].y]);
    }
    cout << res + 1 << endl;
    return 0;
}

by Siegerkranz_2735 @ 2023-01-31 11:37:04

@ttltony ?

by ttltony @ 2023-01-31 11:40:35

@2735 怎么了

by yinhee @ 2023-01-31 11:41:20

@TechnobladePlus f没赋值

by Clay_L @ 2023-01-31 11:42:51

e 我只是想把递归改成递推然后不会 不过栓Q了 @ttltony

by Siegerkranz_2735 @ 2023-01-31 11:45:31

@yinhee 他输入的时候赋值了

by ttltony @ 2023-01-31 11:46:31

@yinhee 他刚刚给f赋值了，赋了极小值，提交后TLE没有解决，还WA了

by Siegerkranz_2735 @ 2023-01-31 11:51:14

你这记忆化没赋值吧

by Clay_L @ 2023-01-31 11:52:33

@2735 ??

by Clay_L @ 2023-01-31 11:53:29

额。。。。

现在的问题是TLE不是WA