滑雪 (搜索)(dp)(贪心)
滑雪 (搜索)(dp)(贪心)
1944864971 发表于2年前
滑雪 (搜索)(dp)(贪心)
  • 发表于 2年前
  • 阅读 6
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购1元起>>>   

以每一点为起点找出所有路径,并求出以此点做为起点的最大路径

求出每个点的最大路径后再找出其中最大的值,输出最大值

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define N 101
using namespace std;
int Hang ,Lie;
int dir[4][2]= {{-1,0},{0,-1},{1,0},{0,1}};//定义四个方向
int len[N][N],map1[N][N];
int dp(int i,int j)
{
if(len[i][j]!=0)return len[i][j];//当前坡度的长度
int s,max1=0;
for(int t=0; t<4; t++)
{
int sx=i+dir[t][0];
int sy=j+dir[t][1];
if(sx>=0&&sx<Hang&&sy>=0&&sy<Lie&&map1[sx][sy]<map1[i][j])//不越界并且小于当前的位置
{
s=dp(sx,sy);//计算以此位置开始的某一条路径的坡度
if(s>max1)max1=s;//找出最大的
}
}
len[i][j]=max1+1;
return max1+1;
}
int main()
{

while(~scanf("%d%d",&Hang,&Lie))
{
memset(len,0,sizeof(len));
for(int i=0; i<Hang; i++)
for(int j=0; j<Lie; j++)
scanf("%d",&map1[i][j]);
int max2=-1;
for(int i=0; i<Hang; i++)
for(int j=0; j<Lie; j++)
{
len[i][j]=dp(i,j);//计算以任意点为起点的最大长度
if(len[i][j]>max2)max2=len[i][j];//再找出最大长度
}
printf("%d\n",max2);
}

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: