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