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]
呢,题目只让求了滑雪的最长距离,两格之间距离算
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 最后不一定停在
by me528963 @ 2020-10-16 12:29:11
@BreezeEnder 哦哦,现在差不多明白了,谢谢大佬啊(ノ゚▽゚)ノ