文章

4

粉丝

0

获赞

8

访问

348

头像
滑雪 题解:
P1568
发布于2026年3月15日 11:46
阅读数 102

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int dp[maxn][maxn];//滑到i,j时的最大长度 
int h[maxn][maxn];
int r,c;
int dir[4][2]={1,0,0,-1,-1,0,0,1};
int dfs(int a,int b){
	if(dp[a][b])return dp[a][b];//已保存直接返回 
	int maxx=1;
	for(int i=0;i<4;i++){ 
		int nx=a+dir[i][0];
		int ny=b+dir[i][1];
		if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&h[nx][ny]>h[a][b]){
			maxx=max(maxx,dfs(nx,ny)+1);//若四个方向有较高的点,先求较高点滑行距离 
		} 
	}
	dp[a][b]=maxx;//记忆化 
	return maxx;
}
int main(){
	while(cin>>r>>c){
		int ans=0;
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				cin>>h[i][j];
			}
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=r;i++){//对每个点枚举求滑行距离 
			for(int j=1;j<=c;j++){
				dp[i][j]=dfs(i,j);
				ans=max(ans,dp[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发