動態(tài)規(guī)劃之經(jīng)典問題——滑雪解題報告
原題鏈接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
Description
Michael喜歡滑雪百這并不奇怪，因?yàn)榛┑拇_很刺激。可是為了獲得速度，滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降機(jī)來載你。Michael想知道載一個區(qū)域中最長底滑坡。區(qū)域由一個二維數(shù)組給出。數(shù)組的每個數(shù)字代表點(diǎn)的高度。下面是一個例子
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
一個人可以從某個點(diǎn)滑向上下左右相鄰四個點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-...-3-2-1更長。事實(shí)上，這是最長的一條。
Input
輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1 <= R,C <= 100)。下面是R行，每行有C個整數(shù)，代表高度h，0<=h<=10000。
Output
輸出最長區(qū)域的長度。
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
個人心得：記得前段時間曾經(jīng)做過一個求最長下降子序列的題（相信大家都做過該題，故不另附原題），如果說說那道題是dp問題的基礎(chǔ)，那么這道題就可以稱得上是求最長下降子序列的變種或者更確切的說是一種升華！
對比來看，前者是求最長下降子序列在一維條件下的解，而1088滑雪這道題則是將此下降問題至于二維平面的背景下。相信弄明白這道題是非常有必要的，因?yàn)樗粌H升華了我們對該類問題的理解，而且能啟發(fā)我們用同樣的思維方式去解決更多動態(tài)規(guī)劃的問題。
題目意思其實(shí)很簡單，給出一個二維數(shù)組，在其中找出一個點(diǎn)，是它能找到一條高度依次下降的路徑并使得這條路徑最長。
算法：開一個二維數(shù)組height記錄每個點(diǎn)的高度，一個二維數(shù)組len記錄每個點(diǎn)能搜索到的最長下降子序列的長度（初始值全為零），一個結(jié)構(gòu)體數(shù)組dot line[20000]記錄每個點(diǎn)的坐標(biāo)（x,y）和高度值 h.
先將每個點(diǎn)的記錄信息保存在結(jié)構(gòu)體數(shù)組中。然后以高度由低到高的順序排序，初始狀態(tài)下指針就位于結(jié)構(gòu)體數(shù)組的起始位置。
接著順序的掃描此結(jié)構(gòu)體數(shù)組內(nèi)的信息，因?yàn)橐呀?jīng)排好序，所以高度是一次遞增的，這樣做的好處是只需要朝著一個方向搜索，而且還可以有效避免越界的問題。
當(dāng)指針每指向一個結(jié)構(gòu)體個體時，我們均可以找到該點(diǎn)在height數(shù)組里的位置，如果存在任意一個點(diǎn)，在它周圍的四個方向上而且高度比該點(diǎn)大且這個任意點(diǎn)的最長下降子序列小于或等于該店的長度。那么這個任意點(diǎn)的最長下降子序列的長度就+1；
等到結(jié)構(gòu)體數(shù)組掃描完成，再去遍歷len這個二維數(shù)組，求出最大值即為所求；
CODE:
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct dot//創(chuàng)建一個結(jié)構(gòu)體存儲每個點(diǎn)的信息
{
int x;
int y;
int h;
};
dot line[20000]; //將每個點(diǎn)存入該結(jié)構(gòu)體數(shù)組
int height[120][120]; //用于存儲input
int len[120][120]; //dp數(shù)組，存儲每個點(diǎn)的最優(yōu)解
int cmp( const void *a ,const void *b) //快速排序的參考函數(shù)
{
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];
}
} //這個雙層循環(huán)用來完成數(shù)據(jù)收集的工作
qsort(line,m*n,sizeof(line[0]),cmp); //對結(jié)構(gòu)體的h參數(shù)進(jìn)行排序
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;
}
} //動態(tài)規(guī)劃過程
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(len[i][j]>max)
max=len[i][j];
}
} //遍歷len數(shù)組，求出最大值
cout<<max+1<<endl;// 因?yàn)槌跏贾凳?,所以最后要加一
return 0;
}
最后不得不說，動態(tài)規(guī)劃的確是一個值得研究的問題，相比于遞歸，他能夠節(jié)省大量的運(yùn)行時間。
鑒于現(xiàn)在還處于學(xué)習(xí)的初級階段，如果有所不足，還請老師和學(xué)長們多多指點(diǎn).
Thank you~