题意：一个R * C的矩阵(1 <= R,C <= 100)，元素代表该点的高度h（0<=h<=10000），从任意点出发，每次只能走上、下、左、右，且将要到的高度要比原高度小，求最长路。

题目链接：http://poj.org/problem?id=1088

――>>设dp[i][j]表示从ij位置出发的最长路，则状态转移方程为：

dp[x][y] = max(dp[x][y], Dp(nNewX, nNewY) + 1);

时间复杂度：O(R * C)

#include 
  
   
#include 
   
     #include 
    
      using std::max; const int MAXN = 100 + 10; int R, C; int nHeight[MAXN][MAXN]; int dp[MAXN][MAXN]; int dx[] = {-1, 1, 0, 0}; int dy[] = { 0, 0, -1, 1}; void Read() { for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { scanf("%d", &nHeight[i][j]); } } } int Dp(int x, int y) { if (dp[x][y] != -1) { return dp[x][y]; } int& nRet = dp[x][y]; nRet = 1; for (int i = 0; i < 4; ++i) { int nNewX = x + dx[i]; int nNewY = y + dy[i]; if (nNewX >= 1 && nNewX <= R && nNewY >= 1 && nNewY <= C && nHeight[nNewX][nNewY] < nHeight[x][y]) { nRet = max(nRet, Dp(nNewX, nNewY) + 1); } } return nRet; } void Solve() { int nRet = 0; memset(dp, -1, sizeof(dp)); for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { if (dp[i][j] == -1) { Dp(i, j); } } } for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { if (dp[i][j] > nRet) { nRet = dp[i][j]; } } } printf("%d\n", nRet); } int main() { while (scanf("%d%d", &R, &C) == 2) { Read(); Solve(); } return 0; }