POJ-1088 滑雪

POJ-1088 滑雪

有一个平面区域，上面有一些点，每个点对应一定的权值，每次移动只能从当前位置向上下左右四个方向中，权值小于当前位置权值的点移动，一次性最多可以移动多远（相邻位置移动一次为1）。

思路:

定义状态 \(f[i][j]\) 表示终点为 \((i,j)\) 的最长路径。

状态转移方程:

for (int i = 0; i < 4; i++)
{
    int tx = x + zb[i][0], ty = y + zb[i][1];
    if (a[x][y] < a[tx][ty])
        f[x][y] = max(f[x][y], dfs(tx, ty) + 1);
}

由于转移方程不仅仅涉及到 \(i - 1\) ，所以采用记忆化搜索的方法来实现。

实现:

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
int f[N][N], a[N][N];
int n, m;
int res = 0;
int zb[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int dfs(int x, int y)
{
    if (x == 0 || y == 0)
        return 0;
    if (f[x][y])
        return f[x][y];
    f[x][y] = 1;
    for (int i = 0; i < 4; i++)
    {
        int tx = x + zb[i][0], ty = y + zb[i][1];
        if (a[x][y] < a[tx][ty])
            f[x][y] = max(f[x][y], dfs(tx, ty) + 1);
    }
    res = max(res, f[x][y]);
    return f[x][y];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dfs(i, j);
    printf("%d\n", res);
    return 0;
}