记忆化为什么一分不得

Ch35 @ 2022-08-15 21:19:13

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105][105],maxx,cnt,dp[105][105];
void dfs(int x,int y){
    maxx=max(maxx,cnt);
    if(dp[x][y]!=0){
        cnt+=dp[x][y]-1;
        maxx=max(maxx,cnt); 
        return ;
    }
    if(x-1>0&&a[x][y]>a[x-1][y]){
        cnt++;
        dp[x-1][y]++;
        dfs(x-1,y);
        cnt--;
    }
    if(y-1>0&&a[x][y]>a[x][y-1]){
        cnt++;
        dp[x][y-1]++;
        dfs(x,y-1);
        cnt--;
    }
    if(y+1<=m&&a[x][y]>a[x][y+1]){
        cnt++;
        dp[x][y+1]++;
        dfs(x,y+1);
        cnt--;
    }
    if(x+1<=n&&a[x][y]>a[x+1][y]){
        cnt++;
        dp[x+1][y]++;
        dfs(x+1,y);
        cnt--;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dfs(i,j);
        }
    }
    cout<<maxx;
    return 0;
}

by Ch35 @ 2022-08-15 21:26:05

补充：记忆化搜索不断地改，结果越改越离谱，甚至几万的大数据也出来了

by SunRises @ 2022-08-15 21:40:38

@Ch35 还在吗

by HarryKane @ 2022-08-15 21:41:29

真·几个月

by Ch35 @ 2022-08-15 21:44:14

@SunRises 还在

by SunRises @ 2022-08-15 21:44:51

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110][110],ans=-1,dp[110][110],nx[5]={0,-1,0,0,1},ny[5]={0,0,-1,1,0};

int dfs(int x,int y){

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

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max(ans,dfs(i,j));
        }
    }
    cout<<ans;
    return 0;
}

by 0x3F @ 2022-08-15 21:51:04

#include <bits/stdc++.h>
#define reg register
#define inl inline
using namespace std;

int R, C, ans;
int arr[110][110], dp[110][110];

inl int dfs(int x, int y) {
    if (x <= 0 || y <= 0 || x > R || y > C) return 0;
    if (dp[x][y]) return dp[x][y];
    int k = 0;
    if (arr[x][y-1] < arr[x][y]) dp[x][y] = max(dp[x][y], dfs(x, y-1));
    if (arr[x-1][y] < arr[x][y]) dp[x][y] = max(dp[x][y], dfs(x-1, y));
    if (arr[x+1][y] < arr[x][y]) dp[x][y] = max(dp[x][y], dfs(x+1, y));
    if (arr[x][y+1] < arr[x][y]) dp[x][y] = max(dp[x][y], dfs(x, y+1));
    dp[x][y]++;
    return dp[x][y];
}

int main() {
    cin >> R >> C;
    for (reg int i = 1; i <= R; i++) {
        for (reg int j = 1; j <= C; j++) {
            cin >> arr[i][j];
        }
    }
    for (reg int i = 1; i <= R; i++) {
        for (reg int j = 1; j <= C; j++) {
            ans = max(ans, dfs(i, j));
        }
    }
    cout << ans << endl;
    return 0;
}

by SunRises @ 2022-08-15 21:54:20

@Ch35 cnt 没必要啊dp数组里存放的应该就是一个点能到达最远的路径长度啊

by SunRises @ 2022-08-15 21:56:20

@Ch35 思路好像有点乱 建议重构吧

by SunRises @ 2022-08-15 22:06:49

@Ch35 在下一步DFS前已经更新了下一步位置的dp数组

dp[x-1][y]++;
dp[x][y-1]++;
dp[x][y+1]++;
dp[x+1][y]++;

下一步DFS就会直接进入if(dp[x][y]!=0)

by Ch35 @ 2022-08-15 22:09:39

@SunRises @0x3F 我AC了，谢谢你们的帮助，我要休息了，早点睡。