记忆化搜索60MLE求助
查看原帖
记忆化搜索60MLE求助
1259694
M0M0楼主2024/9/11 22:23
#include<iostream>
using namespace std;
int a[103][103],dp[103][103];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int r,c;
int dfs(int x,int y){
	if (dp[x][y]!=1) return dp[x][y];
	for (int i = 0;i < 4;i++){
		int px = x + dx[i],py = y + dy[i];
		if (px>r||px<1||py>c||py<1) continue;	
		if (a[x][y]<a[px][py]) continue;
		dfs(px,py);
		dp[x][y] = max(dp[px][py] + 1,dp[x][y]);
	}
	return dp[x][y];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int maxx = -999;
	cin>>r>>c;
	for (int i = 1;i <= r;i++){
		for (int j = 1;j <= c;j++){
			cin>>a[i][j];
			dp[i][j]=1;
		}
	}
	for (int i = 1;i <= r;i++){
		for (int j = 1;j <= c;j++){
			maxx = max(dfs(i,j),maxx);
		}
	}		
	cout<<maxx<<"\n";
}```
#include<iostream>
using namespace std;
int a[103][103],dp[103][103];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int r,c;
int dfs(int x,int y){
	if (dp[x][y]!=1) return dp[x][y];
	for (int i = 0;i < 4;i++){
		int px = x + dx[i],py = y + dy[i];
		if (px>r||px<1||py>c||py<1) continue;	
		if (a[x][y]<a[px][py]) continue;
		dfs(px,py);
		dp[x][y] = max(dp[px][py] + 1,dp[x][y]);
	}
	return dp[x][y];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int maxx = -999;
	cin>>r>>c;
	for (int i = 1;i <= r;i++){
		for (int j = 1;j <= c;j++){
			cin>>a[i][j];
			dp[i][j]=1;
		}
	}
	for (int i = 1;i <= r;i++){
		for (int j = 1;j <= c;j++){
			maxx = max(dfs(i,j),maxx);
		}
	}		
	cout<<maxx<<"\n";
}
2024/9/11 22:23
加载中...