洛谷 P1434 滑雪
2024-10-20 17:22:24
题目描述
Michael喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可行的滑坡为24-17-16-1(从24开始,在1结束)。当然25-24-23―┅―3―2―1更长。事实上,这是最长的一条。
输入输出格式
输入格式:
输入的第一行为表示区域的二维数组的行数R和列数C(1≤R,C≤100)。下面是R行,每行有C个数,代表高度(两个数字之间用1个空格间隔)。
输出格式:
输出区域中最长滑坡的长度。
输入输出样例
输入样例#1:
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例#1:
25
记忆化搜索
#include <cstdio>
int R,C,maxn=;
int hei[][],f[][],fx[]={,-,,},fy[]={,,-,};
int max(int a,int b)
{
return a>b?a:b;
}
int dfs(int x,int y)
{
if(f[x][y]) return f[x][y];
int p=;
for(int i=;i<;i++)
{
int tx=x+fx[i],ty=y+fy[i];
if(tx>=&&tx<=R&&ty>=&&ty<=C&&hei[tx][ty]>hei[x][y]) p=max(dfs(tx,ty),p);
}
f[x][y]=p+;
return f[x][y];
}
int main()
{
scanf("%d%d",&R,&C);
for(int i=;i<=R;i++)
for(int j=;j<=C;j++)
scanf("%d",&hei[i][j]);
for(int i=;i<=R;++i)
for(int j=;j<=C;++j)
maxn=max(maxn,dfs(i,j));
printf("%d",maxn);
}
最新文章
- 批量插入数据 C# SqlBulkCopy使用
- 八大排序算法之六--交换排序—快速排序(Quick Sort)
- URPF 简单流程
- .net抓取网页数据
- sqlserver 数据库里面金额类型为什么不建议用float,实例告诉你为什么不能。
- J2SE知识点摘记(十)
- 【转】Jmeter(三)-简单的HTTP请求(非录制)
- Volist标签
- java线程池原理及实现方式
- MySQL学习笔记_9_MySQL高级操作(上)
- 分配swap分区
- [poj P1475] Pushing Boxes
- Python(五) 字典
- Linux - 系统资源
- 数据库备份-SQL Server 维护计划
- UserInfoActivity用户图像修改和退出登录
- 设置邮箱发送服务|邮箱开始SMTP服务和腾讯云解封25端口的经验总结
- NOI.AC WC模拟赛
- vim自定义配置之nerdTree
- postman请求失败
热门文章
- Linux Shell高级技巧(目录)
- JAVA 布局控制
- vue 使用font-awesome 只需两步
- web_html-day1
- 用 SDL2 处理精灵图
- Integrate Your Code with the Frameworks---整合你的代码和框架
- android 在一个应用中启动另一个应用
- c#删除指定文件夹中今天之前的文件
- Python解释器的安装步骤
- bug日志-天坑,Spring Security的登陆报错:An internal error occurred while trying to authenticate the user.