滑雪(记忆化搜索)
作者:
amagi
,
2023-05-16 18:24:27
,
所有人可见
,
阅读 126
#include <iostream>
#include <cstring>
using namespace std;
int m,n;
const int N = 1001;
int x[N][N],y[N][N];
int dx[] = {0,-1,0,1},dy[] = {-1,0,1,0};
int dp(int a,int b){
int &v = y[a][b];
if(v != -1) return v;
v = 1;
for(int i = 0; i < 4; i ++){
int aa = a + dx[i];
int bb = b + dy[i];
if(aa >= 1 && aa <= m && bb >= 1 && bb <= n && x[aa][bb] < x[a][b]){
v = max(v,dp(aa,bb) + 1);
}
}
return v;
}
void slove(){
cin >> m >> n;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++) cin >> x[i][j];
}
memset(y,-1,sizeof y);
int res = 0;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++){
res = max(res,dp(i,j));
}
}
cout << res << endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
slove();
return 0;
}