记忆化搜索,#2TLE了,大佬帮忙看看,谢谢
查看原帖
记忆化搜索,#2TLE了,大佬帮忙看看,谢谢
772478
Wisdom_chicken_god楼主2023/1/9 11:58
#include<bits/stdc++.h>
#define RC 105
using namespace std;
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	inline long long read(){
		char ch=gh();
		long long x=0;
		bool t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
using IO::read;
int xy[5][3]={{0,1},{0,-1},{1,0},{-1,0}};
int r,c,ux[RC][RC],f[RC][RC];
bool b[RC][RC];
int dfs(int i,int j){
	if(b[i][j]==1)
	return f[i][j];
	int k=1;
	f[i][j]=1;
	for(int ko=0;ko<=3;ko++){
		int q=i+xy[ko][0];
		int w=j+xy[ko][1];
		if(ux[i][j]>ux[q][w]&&q>=1&&q<=r&&w>=1&&w<=c)
		{
			f[i][j]=max(dfs(q,w)+1,f[i][j]);
		}
	}
	return f[i][j];
}
int main(){
	r=read();c=read();
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			ux[i][j]=read();
		}
	}
	int ans=-1;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			int df=dfs(i,j);
			if(ans<df)
			ans=df;
		}
	}
	write(ans);
	return 0;
}
2023/1/9 11:58
加载中...