OpenJudge/Poj 1088 滑雪
2024-10-15 23:49:31
1.链接地址:
bailian.openjudge.cn/practice/1088
http://poj.org/problem?id=1088
2.题目:
- 总Time Limit:
- 1000ms
- Memory Limit:
- 65536kB
- Description
- 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。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
- Input
- 输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
- Output
- 输出最长区域的长度。
- Sample Input
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- Sample Output
25- Source
- Don't know
3.思路:
动态规划,先按照高度降序排序,再依次计算
刚开始想当然,以为从最高高度寻找一个路径一定是最长,所以使用了优先队列+广搜,白白WA了一次
4.代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib> using namespace std; struct PATH
{
int x;
int y;
int height;
}; int cmp(const void* a,const void *b)
{
PATH *p1 = (PATH *) a;
PATH *p2 = (PATH *) b;
return p2->height - p1->height;
} int main()
{
//freopen("C://input.txt","r",stdin); int r,c;
cin >> r >> c; int i,j; int **arr_height = new int*[r];
for(i = ; i < r; ++i) arr_height[i] = new int[c]; int **arr_mark = new int*[r];
for(i = ; i < r; ++i)
{
arr_mark[i] = new int[c];
memset(arr_mark[i],,sizeof(int) * c);
} PATH *arr_path = new PATH[r * c]; for(i = ; i < r; ++i)
{
for(j = ; j < c; ++j)
{
cin >> arr_height[i][j];
arr_path[i * c + j].x = j;
arr_path[i * c + j].y = i;
arr_path[i * c + j].height = arr_height[i][j];
}
} qsort(arr_path,r * c,sizeof(PATH),cmp); int idx_x[] = {-,,,};
int idx_y[] = {,,,-}; int res = ;
for(i = ; i < r * c; ++i)
{
//cout << arr_path[i].height << " " << arr_path[i].x << " " << arr_path[i].y << endl; int max = ;
for(j = ; j < ; ++j)
{
int temp_x = arr_path[i].x + idx_x[j];
int temp_y = arr_path[i].y + idx_y[j]; if(temp_x < || temp_x >= c || temp_y < || temp_y >= r) continue; if(arr_height[temp_y][temp_x] > arr_height[arr_path[i].y][arr_path[i].x] && max < arr_mark[temp_y][temp_x])
{
max = arr_mark[temp_y][temp_x];
}
} arr_mark[arr_path[i].y][arr_path[i].x] = max + ;
if(res < max + ) res = max + ;
} cout << res << endl; delete [] arr_path; for(i = ; i < r; ++i) delete [] arr_height[i];
delete [] arr_height; for(i = ; i < r; ++i) delete [] arr_mark[i];
delete [] arr_mark; return ;
}
最新文章
- Java基础-服务器的发送和接收
- Oracle Recovery 01 - 常规恢复之完全恢复
- Python里的编码问题
- AFNetworking 与 UIKit+AFNetworking 详解
- Redis 安装,主从配置及Sentinel配置自动Failover
- ubutu之Navicat安装
- 前端里神奇的BFC 原理剖析
- Unity3D 中 用quaternion 来对一个坐标点进行旋转的初步体会
- Python3学习(1)-基础篇
- C#(结构体_枚举类型)
- 软件测试入门——测试模型(V型 W型 H型)
- 【LeetCode】217 &; 219 - Contains Duplicate &; Contains Duplicate II
- 通过SQL Server 2008 访问MySQL(转)
- android adb:电池与电量
- IE下空链接失效原因及解决方法
- spring 初始化
- vue内置指令与自定义指令
- Build a Machine Learning Portfolio(构建机器学习投资组合)
- jvisualVM的使用
- 13-03 Java 基本类型包装类概述,Integer类,Character