动态规划之经典问题——滑雪解题报告
原题链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
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
个人心得：记得前段时间曾经做过一个求最长下降子序列的题（相信大家都做过该题，故不另附原题），如果说说那道题是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~