只会用dfs的记忆化搜索做,还有别的方法吗(第一次接触dp)
查看原帖
只会用dfs的记忆化搜索做,还有别的方法吗(第一次接触dp)
787834
QUYI楼主2023/3/7 13:15
#include<stdio.h>
int num[105][105];
int r,c;
int a[]={-1,0,0,1},b[]={0,-1,1,0};
int droad[105][105];
int road(int x,int y,int ans){
	if(x<0||y<0||x>=r||y>=c){
		return ans;
	}
	if(droad[x][y]!=-1){
		return droad[x][y];
	}
	int max=0;
	for(int i=0;i<4;i++){
		int xx=x+a[i];
		int yy=y+b[i];
		if(xx<0||yy<0||xx>=r||yy>=c){
			continue;
		}
		if(num[x][y]>num[xx][yy]){
			droad[xx][yy]=road(xx,yy,1);
			if(droad[xx][yy]>max){
				max=droad[xx][yy];
			}
		}
	}
	ans+=max;
	return ans;
}
int main() {
	scanf("%d%d",&r,&c);
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			scanf("%d",&num[i][j]);
			droad[i][j]=-1;
		}
	}
	int max=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			int temp=road(i,j,1);
			if(temp>max){
				max=temp;
			}
		}
	}
	printf("%d",max);
	return 0;
}
2023/3/7 13:15
加载中...