原题链接:https://www.luogu.com.cn/problem/P1434
题意解读:计算能滑行的最长距离。
解题思路:
设dp(i, j)表示从i,j可以滑行的最大距离
对于4个方向i,j可以到达的点,ni,nj,如果可以滑过去(ni,ni所在点高度更低)
则dp(i, j) = max(dp(i, j), 1 + dp(ni, nj))
为了便于搜索4个方向的各条路径,采用dfs递归形式更便于操作
而每个点所能滑行的最大距离在递归过程中会多次重复计算,因此可以采用记忆化搜索,保存已经计算过的结果。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int r, c;
int a[N][N], f[N][N];
bool flag[N][N];
int ans;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
//从x,y开始能滑行的最大距离
int dp(int x, int y)
{
if(f[x][y]) return f[x][y]; //记忆化,如果已经计算过直接返回
int res = 1; //任意点可以滑行的初始距离为1
flag[x][y] = true;
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(!flag[nx][ny] && nx >= 1 && nx <= r && ny >= 1 && ny <= c && a[nx][ny] < a[x][y])
{
flag[nx][ny] = true;
res = max(res, 1 + dp(nx, ny)); //dfs搜索所有路径,取长度最大的
flag[nx][ny] = false;
}
}
return f[x][y] = res; //记忆化,保存滑行距离
}
int main()
{
cin >> r >> c;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
cin >> a[i][j];
for(int i = 1; i <= r; i++)
{
for(int j = 1; j <= c; j++)
{
memset(flag, 0, sizeof(flag)); //重置flag
ans = max(ans, dp(i, j)); //从每一个点开始dfs搜索路径
}
}
cout << ans;
return 0;
}
标签:ni,int,洛谷题,滑行,nx,ny,P1434,SHOI2002,dp From: https://www.cnblogs.com/jcwy/p/18143989