POJ1088 滑雪

题目要求某个点的滑坡距离最大，要想滑坡距离最大那么这个点的高度就要最高，因为高度最高，他就可以滑向任意一个它四周点，当然也要滑向在它的四周中高度最高的那个点。
我们可以定义dp[i][j]的状态为从i，j滑下去的最高长度，那么状态转移方程为dp[i][j]=max(dp[i][j],dp[i-1][j]+1)
dp[i][j]=max(dp[i][j],dp[i+1][j]+1),max(dp[i][j],dp[i][j-1]+1),max(dp[i][j],dp[i][j+1]+1)，即dp[i][j]的最大值就是它滑向在它的四周中的最大值的那个点

#include <iostream>
using namespace std;
const int maxn = 105;
int arr[maxn][maxn];
int dp[maxn][maxn];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int n, m;
int res = 0;
int calc(int x, int y) {
    if (dp[x][y] != 0)return dp[x][y];
    dp[x][y]=1;
    for (int i = 0; i < 4; i++) {
        int newx = x + dir[i][0];
        int newy = y + dir[i][1];
        if (newx >= 1 && newx <= n && newy >= 1 && newy <= m&&arr[x][y]>arr[newx][newy]) {
            dp[x][y] = max(dp[x][y], calc(newx, newy) + 1);
        }
    }
    res = max(res, dp[x][y]);
    return dp[x][y];
}
int main()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            calc(i, j);
        }
    }
    cout << res;
}