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;
}
标签:tx,ty,int,res,zb,1088,POJ,滑雪
From: https://www.cnblogs.com/zxr000/p/16998032.html