【求助】求问这两种记忆化搜索方法的区别

P1434 [SHOI2002] 滑雪

me528963 @ 2020-10-15 23:49:46

rt,下面是蒟蒻写的两种记忆化搜索的代码: code1:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105;
ll rec[N][N];
int r,n;
ll f[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
ll findroute(int i,int j){
    if(f[i][j])
        return f[i][j];
    f[i][j] = 1;
    for (int t = 0; t < 4;t++){
        int x = i + dx[t], y = j + dy[t];
        if((x>0 && y>0 && x<=r && y<=n) && rec[x][y]<rec[i][j]){
            f[i][j]=max(f[i][j],(findroute(x, y)+1));
        }
    }
    return f[i][j];
}
int main(){
    memset(f, 0, sizeof(f));
    cin >> r >> n;
    for (int i = 1; i <= r;i++){
        for (int j = 1; j <= n;j++){
            cin >> rec[i][j];
        }
    }
    ll ans = 0;
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= n;j++){
            ans = max(ans, findroute(i, j));
        }
    }
    cout << ans << endl;
}

code2(只有findroute代码不同)

ll findroute(int i,int j){
    if(f[i][j])
        return f[i][j];    
    if(rec[i][j]==1){
        f[i][j]+=1;
        return f[i][j];
     }
     ll ans = 0;
    for (int t = 0; t < 4;t++){
        int x = i + dx[t], y = j + dy[t];
        if((x>0 && y>0 && x<=r && y<=n) && rec[x][y]<rec[i][j]){
            ans=max(ans,(findroute(x, y)+rec[i][j]-rec[x][y]));
        }
    }
    f[i][j] = ans;
    return f[i][j];
}

code1是参考讨论区里的大佬的回答修改的,code2是自己最初写的,最后code1能够AC,而code2只能过三个点,请问这两种的差别在哪里,先谢谢回答的大佬了


by Ryo_Yamada @ 2020-10-16 06:44:22

@me528963 为什么是 findroute(x, y) + rec[i][j] - rec[x][y] 呢,题目只让求了滑雪的最长距离,两格之间距离算 1


by me528963 @ 2020-10-16 11:14:02

@BreezeEnder 因为我看题目里没有说,就想着会不会有间隔不为1的数据存在,然而改为 ans=max(ans,(findroute(x, y)+1));的话,最后还是30分(/ω\)


by Ryo_Yamada @ 2020-10-16 11:19:37

@me528963 最后不一定停在 1 处,所以 ans 初始化成 1


by me528963 @ 2020-10-16 12:29:11

@BreezeEnder 哦哦,现在差不多明白了,谢谢大佬啊(ノ゚▽゚)ノ


|