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 SunRises @ 2022-08-15 22:10:22
@Ch35 OK