题解 | #滑雪#

这题动规

如果用递推来实现的话，就得按点由低到高确定（先给点排序）...

如果用记忆化搜索来写，就可以避免上述顺序的麻烦惹

特别注意的是边界的处理呀，当访问到列或行是0的时候是不要赋值f[tx][ty]为1的qwq

#include<iostream>
#include<algorithm>
using namespace std;
int ans,n,m,a[110][110],f[110][110],dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int calc(int x,int y){
	if(f[x][y])return f[x][y];//确定了就直接返回 
	f[x][y]=1;//首先自己肯定是一个长度 
	for(int i=0;i<4;i++){
		int tx=x+dx[i],ty=y+dy[i];
		if(a[tx][ty]<a[x][y]&&tx&&ty)//避免了进入f[0][y]/f[x][0]=1而对后面造成影响 
			f[x][y]=max(f[x][y],calc(tx,ty)+1);
	}
	return f[x][y];
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	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++)
			ans=max(ans,calc(i,j));
	cout<<ans;
	return 0;
}