一、有两种思路:
1)根据记忆搜索(保存了最优值表格),在纯粹的递归思路里加入记忆表格。
2)先将高度排序,然后依次从点由低到高 计算 该点的最长路径长度。(因为当矮点不可能通过高点,而比当前矮的点都在之前计算好了)
--------------------------------------------
二、关于最优路径构建
将点的最大路径长度依赖的点的(dx,dy) 即 行、列的增量存储在一个表格中。
Language:
Default
滑雪
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 50449 |
|
Accepted: 18324 |
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
SHTSC 2002
#include <stdio.h>
int r,c;
//#define MAX 102
int height[102][102];
int length[102][102];
int FindMaxLength(int i,int j)
{
if(length[i][j]>0)
return length[i][j];
int tmp1=0;
int tmp2=0;
int tmp3=0;
int tmp4=0;
//left
if(j>=2)
if(height[i][j-1]<height[i][j])
tmp1=1+FindMaxLength(i,j-1);
//right
if(j<=c-1)
if(height[i][j+1]<height[i][j])
tmp2=1+FindMaxLength(i,j+1);
//up
if(i>=2 )
if( height[i-1][j]< height[i][j])
tmp3=1+FindMaxLength(i-1,j);
//down
if(i<=r-1 )
if(height[i+1][j]<height[i][j])
tmp4=1+FindMaxLength(i+1,j);
int max=0;
if(tmp1>max)
{
max=tmp1;
}
if(tmp2>max)
{
max=tmp2;
}
if(tmp3>max)
{
max=tmp3;
}
if(tmp4>max)
{
max=tmp4;
}
return max;
}
int main()
{
scanf("%d",&r);
scanf("%d",&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
scanf("%d",&height[i][j]);
length[i][j]=0;
}
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
length[i][j]=FindMaxLength(i,j);
}
int max=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(length[i][j]>max)
{
max=length[i][j];
}
}
max=max+1;
printf("%d\n",max);
scanf("%d",&r);
return 0;
}
增加 最优路径的代码:
|
分享到:
相关推荐
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
百练POJ1088滑雪问题的源代码,C写的,不过后缀是.cpp。写的还算比较易懂,呵呵
poj 1088 滑雪 代码,记忆化搜索
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
西北工业大学-c语言-POJ-题目及答案-第七季.doc
整理的acm知识分类 ACM-POJ 算法训练指南
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
北大POJ初级-动态规划 解题报告+AC代码
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
An solution of a problem using Splay Trees
acm的好资料
poj acm通过的水题 完美动态规划和递归的应用,欢迎查看分享
水题, 爆搜const int maxn = 105;
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
坐标型动态规划 poj1191棋盘分割 poj1088滑雪 noi过河卒 动态规划的解题思想及思路
POJ水题集-----50道左右-----增加自信啊..
北大POJ2002-Squares 解题报告+AC代码