記憶化搜索解決POJ 1088
Description
Michael喜歡滑雪百這并不奇怪， 因為滑雪的確很刺激。可是為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區域中最長底滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。下面是一個例子
一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。
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[][]數組
要存入什么樣的數據呢？那不是說空話嗎？
狀態轉移方程：dp[x][y]=max(dp[x-1][y], dp[x+1][y], dp[x][y-1], dp[x][y+1])+1
狀態轉移方程的表現形式是多樣的，不一定非要用類似上面的式子來體現出來。
比如本題的表現方式。
View Code
#include<iostream> using namespace std; int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; int n,m; int map[102][102]; int dp[102][102]; int dfs(int x,int y) { //cout <<x << " " << y << endl; int tx,ty,i; if(dp[x][y]) //當已經搜索過時就返回 return dp[x][y]; for(i = 0;i < 4;i++) { tx = x + dir[i][0] , ty = y + dir[i][1]; if(tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] < map[x][y])//搜索+ 狀態轉移方程 { int temp = dfs(tx,ty); //遞歸的出口有兩個1.在11行；2.在16行 if(dp[x][y] <= temp) //i=0時比較dfs(x+1, y);i=1時比較dfs(x, y+1);i=2時比較dfs(x-1, y);i=3時比較dfs(x, y-1) { dp[x][y] = temp+1; } } } return dp[x][y]; } int main() { int i,j,t; while(cin >> n >> m) { for(i =0 ;i < n;i++) { for(j = 0;j < m;j++) { cin >> map[i][j]; dp[i][j] = 0; } } int max = -1; for(i = 0 ;i < n;i++) { for(j = 0;j < m;j++) { t = dfs(i,j); if(max < t) { max = t; } } } cout <<max + 1 << endl; } return 0; }
posted on 2011-09-05 08:01 More study needed. 閱讀(1610) 評論(0) 收藏 舉報
浙公網安備 33010602011771號