The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1088 动态规划之经典问题——滑雪

动态规划之经典问题——滑雪解题报告

                                           

原题链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1088

Description

Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

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

个人心得:记得前段时间曾经做过一个求最长下降子序列的题(相信大家都做过该题,故不另附原题),如果说说那道题是dp问题的基础,那么这道题就可以称得上是求最长下降子序列的变种或者更确切的说是一种升华!

对比来看,前者是求最长下降子序列在一维条件下的解,而1088滑雪这道题则是将此下降问题至于二维平面的背景下。相信弄明白这道题是非常有必要的,因为它不仅升华了我们对该类问题的理解,而且能启发我们用同样的思维方式去解决更多动态规划的问题。

 

 

题目意思其实很简单,给出一个二维数组,在其中找出一个点,是它能找到一条高度依次下降的路径并使得这条路径最长。

算法:开一个二维数组height记录每个点的高度,一个二维数组len记录每个点能搜索到的最长下降子序列的长度(初始值全为零),一个结构体数组dot line[20000]记录每个点的坐标(x,y)和高度值 h.

先将每个点的记录信息保存在结构体数组中。然后以高度由低到高的顺序排序,初始状态下指针就位于结构体数组的起始位置。

接着顺序的扫描此结构体数组内的信息,因为已经排好序,所以高度是一次递增的,这样做的好处是只需要朝着一个方向搜索,而且还可以有效避免越界的问题。

当指针每指向一个结构体个体时,我们均可以找到该点在height数组里的位置,如果存在任意一个点,在它周围的四个方向上而且高度比该点大且这个任意点的最长下降子序列小于或等于该店的长度。那么这个任意点的最长下降子序列的长度就+1;

等到结构体数组扫描完成,再去遍历len这个二维数组,求出最大值即为所求;

 

 

 

CODE:

 

#include<iostream>

#include
<cmath>

#include
<cstring>

#include
<cstdio>

#include
<algorithm>

using namespace std;

 

 

struct dot//创建一个结构体存储每个点的信息

{

    
int x;

    
int y;

    
int h;

}
;

dot line[
20000]; //将每个点存入该结构体数组

int height[120][120]; //用于存储input

int len[120][120];  //dp数组,存储每个点的最优解

int cmp( const void *a ,const void *b) //快速排序的参考函数

{

 

    
if((*(dot *)a).h>(*(dot *)b).h)

        
return 1;

    
else return -1;

 

}


int main ()

{

    
int m,n;

    cin
>>m>>n;

    
int i,j;

    
int flag=-1;

    
int max=0;

    
for(i=1;i<=m;i++)

    
{

 

        
for(j=1;j<=n;j++)

        
{

            flag
++;

            scanf(
"%d",&height[i][j]);

            line[flag].x
=i;

            line[flag].y
=j;

            line[flag].h
=height[i][j];

        }


    }
 //这个双层循环用来完成数据收集的工作

    qsort(line,m
*n,sizeof(line[0]),cmp); //对结构体的h参数进行排序

    
for(i=0;i<m*n;i++)

    
{

    
if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y+1]&&len[line[i].x][line[i].y]>=len[line[i].x][line[i].y+1])

        
{

            len[line[i].x][line[i].y
+1]=len[line[i].x][line[i].y]+1;

        }


    
if(height[line[i].x][line[i].y]<height[line[i].x+1][line[i].y]&&len[line[i].x][line[i].y]>=len[line[i].x+1][line[i].y])

        
{

            len[line[i].x
+1][line[i].y]=len[line[i].x][line[i].y]+1;

        }


    
if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y-1]&&len[line[i].x][line[i].y]>=len[line[i].x][line[i].y-1])

        
{

            len[line[i].x][line[i].y
-1]=len[line[i].x][line[i].y]+1;

        }


        
if (height[line[i].x][line[i].y]<height[line[i].x-1][line[i].y]&&len[line[i].x][line[i].y]>=len[line[i].x-1][line[i].y])

        
{

            len[line[i].x
-1][line[i].y]=len[line[i].x][line[i].y]+1;

        }


    }
 //动态规划过程

    
for(i=1;i<=m;i++)

    
{

        
for(j=1;j<=n;j++)

        
{

 

           

            
if(len[i][j]>max)

                max
=len[i][j];

        }


    }
 //遍历len数组,求出最大值

    cout
<<max+1<<endl;// 因为初始值是0,所以最后要加一

    
return 0;

}


 

 

最后不得不说,动态规划的确是一个值得研究的问题,相比于递归,他能够节省大量的运行时间。

鉴于现在还处于学习的初级阶段,如果有所不足,还请老师和学长们多多指点.

Thank you~

posted on 2009-02-19 13:00 abilitytao 阅读(10572) 评论(13)  编辑 收藏 引用

评论

# re: POJ 1088 动态规划之经典问题——滑雪 2009-02-19 21:43 ghbxx

PKU上还有一个题目和他很相似的,希望楼主能做一下。我在大学的时候做过的。  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2009-02-19 23:10 abilitytao

@ghbxx
请问学长你说的是求长下降子序列吗
还是最大子段和?
  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪[未登录] 2009-02-22 20:30 Philip85517

更像是一个迭代的过程。Ps.四个方向的搜索写的太长了,完全可以用数组来表示方向,会快很多。
相似的题目:FatMouse and Cheese, Monkey and banana
有兴趣再看看那个Fourier's Lines,个人感觉不错,是一个比较好的Dp
  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪[未登录] 2009-02-22 20:41 abilitytao

@Philip85517
谢谢
  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2009-04-21 17:56 Wpl

我也在努力学习DP,感觉好难啊  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2009-04-23 17:59 你好

好感谢,真了无头绪之中  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2009-06-11 11:23 hfie

思路很强大,但不像是最长下降子序列  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2009-11-15 13:01 PhiloEve

不需要调用那么多的库吧?  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2010-11-25 11:30 aaa

您好,我感觉您用的是搜索啊,不是DP啊,我是初学者,不了解,请您指教
xuzhenjetxu@gmail.com  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2011-06-17 01:10 Dev|il

@aaa
是DP  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2012-05-24 00:49 hacker003

感谢楼主,此题确实是好题。
不过楼主的搜索确实可以把代码简化一下  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪[未登录] 2012-05-24 14:35 abilitytao

@hacker003
刚开始学的时候写的 比较水 呵呵 见笑了...  回复  更多评论   

# re: POJ 1088 动态规划之经典问题——滑雪 2013-07-13 14:08 aaa

楼主提交过么???WA啊。。。有考虑过有两条相等的路么???比如
1 2
2 3
你的程序算出来是3
但应该是2 啊  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理