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

嗯嗯，這是我的第二道動態規劃題，實在感覺和前一道很像啊，然后就直接做了。
我分析一下：記憶化搜索+遞歸。
1、起點是未知的，所以要遍歷每一個起點，最后記錄最大值。
2、圖形是有邊界的，必須滿足按照嚴格下降的條件，才能走到周圍的點。
3、然后就沒有了。 1 #include<iostream> 2 #include<string.h> 3 #define maxn 100+5 4 using namespace std; 5 int xx[4]={0,0,-1,1}; 6 int yy[4]={-1,1,0,0}; 7 int d[maxn][maxn]; 8 int v[maxn][maxn]; 9 int dp(int x,int y,int n,int m){ 10 if(d[x][y]>0) return d[x][y]; 11 d[x][y]=1; 12 for (int i=0;i<4;i++){ 13 int nx=x+xx[i]; 14 int ny=y+yy[i]; 15 if (nx>n || ny>m || nx<1 || ny<1 || v[nx][ny]>=v[x][y]) continue; 16 d[x][y]=max(d[x][y],dp(nx,ny,n,m)+1); 17 } 18 return d[x][y]; 19 } 20 int main(){ 21 int n,m; 22 while(cin>>n>>m){ 23 for(int i=1;i<=n;i++){ 24 for(int j=1;j<=m;j++){ 25 cin>>v[i][j]; 26 } 27 } 28 int ans=0; 29 memset(d,0,sizeof(d)); 30 for(int i=1;i<=n;i++){ 31 for(int j=1;j<=m;j++){ 32 ans=max(ans,dp(i,j,n,m)); 33 } 34 } 35 cout<<ans<<endl; 36 } 37 38 }

?

轉載于:https://www.cnblogs.com/little-w/p/3223288.html

總結

以上是生活随笔為你收集整理的动态规划 POJ 1088 滑雪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。