滑雪

題目描述

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更長。事實上，這是最長的一條。

關于輸入

輸入的第一行表示區域的行數R和列數C(1<=R,C<=500)。下面是R行，每行有C個整數，代表高度h，0<=h<=1000000。

關于輸出

輸出最長區域的長度。

例子輸入

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

例子輸出

25

解題分析

起初一看，覺得是一個用DFS深度優先搜索的題無疑了，于是用一個go函數，并遍歷每個位置，從每個位置開始搜索，并時刻更新搜索的長度和保留最大值，同時，也合理地存儲了當前位置下的長度，并在其他搜索路徑經過此處時，判斷長度是否要更小，如果更小，說明這是一種無效的情況，可以提前退出減枝操作。于是有了下面的代碼:

代碼演示1

#include <iostream>
using namespace std;
int R,C,mountains[505][505],res[505][505];
int ans=1,dx[]={-1,1,0,0},dy[]={0,0,-1,1};void go(int x,int y,int step){if(step>ans){ans=step;}if(step<=res[x][y]){return;}for(int i=0;i<4;i++){int nx=dx[i]+x,ny=dy[i]+y;if(nx>=0 && nx<R && ny>=0 && ny<C && mountains[nx][ny]<mountains[x][y]){go(nx,ny,step+1);}}res[x][y]=step;return;
}int main(){scanf("%d%d",&R,&C);for(int i=0;i<R;i++)for(int j=0;j<C;j++){scanf("%d",&mountains[i][j]);}for(int i=0;i<R;i++)for(int j=0;j<C;j++){go(i,j,1);}printf("%d",ans);return 0;
}

首先，本代碼在思路以及算法的實現上都不存在問題，總的來說，這是個正確的代碼。不過，它有個致命的缺陷，就是在一些特定的情況下遞歸深度會過大，從而導致棧溢出，programerror！實際上，我們也許根本不用調用那么多棧。

于是來看動態規劃的思路：

我們假定dp[i][j]是從(i,j)位置開始尋找所能到達的最大長度，我們可以發現，dp[i][j]=max(dp[x-1][y]+1,dp[x+1][y]+1,dp[x][y-1]+1,dp[x][y+1]+1)，于是動態規劃的轉移方程就出來啦。當前位置所能遞推的最大深度，就是它周圍格子所能遞推的最大深度再+1就可以了。

代碼實現

#include <iostream>
using namespace std;
int R,C,mountains[505][505],dp[505][505];
int ans=1,dx[]={-1,1,0,0},dy[]={0,0,-1,1};int go(int x,int y){if(dp[x][y]){return dp[x][y];}int step=1;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0 && nx<R && ny>=0 && ny<C && mountains[nx][ny]<mountains[x][y]){step=max(step,go(nx,ny)+1);}}return dp[x][y]=step;
}int main(){scanf("%d%d",&R,&C);for(int i=0;i<R;i++)for(int j=0;j<C;j++){scanf("%d",&mountains[i][j]);}for(int i=0;i<R;i++)for(int j=0;j<C;j++){ans=max(ans,go(i,j));}printf("%d",ans);return 0;
}