题目地址：http://poj.org/problem?id=1088
题目大意：给你一个m*n的矩阵 如果其中一个点高于另一个点 那么就可以从高点向下滑 直到没有可以下滑的时候 就得到一条下滑路径 求最大的下滑路径
分析：因为只能从高峰滑到低峰，无后效性，所以每个点都可以找到自己的最长下滑距离（只与自己高度有关）。记忆每个点的最长下滑距离，当有另一个点的下滑路径遇到这个点的时候，直接加上这个点的最长下滑距离。
dp递推式是，dp[x][y] = max(dp[x][y],dp[x+1][y]+1,dp[x][y-1]+1,dp[x-1][y]+1,dp[x][y+1]+1);
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 //dp[x][y]表示 (x,y)这个点的最长下滑路径 5 using namespace std; 6 const int maxn = 102; 7 using namespace std; 8 int n, m,bx,by,ans; 9 int G[maxn][maxn]; 10 int dp[maxn][maxn]; 11 int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//这种图的搜索 可以把方向写在一个数组中 使代码更简洁 12 int dfs(int x, int y) 13 { 14 if(dp[x][y])//如果之前已经有结果 那么直接使用 15 { 16 return dp[x][y]; 17 } 18 for(int i = 0; i < 4;i++) 19 { 20 int tx = x,ty = y; 21 tx += dir[i][0]; 22 ty += dir[i][1]; 23 // 下面2个if都是排除非法情况 24 if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue; 25 if(G[tx][ty] >= G[x][y]) continue; 26 // 如果四周的点都比自己高 或者路径长没自己长 那么不更新 否则更新为四周的点+1 27 dp[x][y] = max(dp[x][y],dfs(tx,ty)+1); 28 } 29 return dp[x][y]; 30 31 } 32 int main() 33 { 34 35 scanf("%d %d", &n,&m); 36 for(int i = 0;i < n; i++) 37 { 38 for(int j = 0; j < m; j++) 39 { 40 scanf("%d", &G[i][j]); 41 42 } 43 } 44 ans = 0; 45 for(int i =0; i < n; i++) 46 { 47 for(int j = 0; j < m; j++) 48 dfs(i,j); 49 } 50 for(int i =0; i < n; i++) 51 { 52 for(int j = 0; j < m; j++) 53 ans = max(ans,dp[i][j]); 54 } 55 printf("%d",ans+1);//因为自己也算做一步 所以ans+1 56 57 return 0; 58 }