张家界网站建设方案,长沙房产网官网,太原手机模板建站,北京建站工作室【解题思路】 1. 状态定义 状态定义#xff1a;dp[i][j]#xff1a;从(i,j)出发的所有路线中#xff0c;长度最长的路线的长度。
2. 状态转移方程 记第(i,j)位置的高度为a[i][j]。 集合#xff1a;从(i,j)出发的所有路线 分割集合#xff1a;根据下一步可以到达的位置分割…【解题思路】 1. 状态定义 状态定义dp[i][j]从(i,j)出发的所有路线中长度最长的路线的长度。
2. 状态转移方程 记第(i,j)位置的高度为a[i][j]。 集合从(i,j)出发的所有路线 分割集合根据下一步可以到达的位置分割集合。 下一步可以到达的位置有(i-1,j), (i1,j), (i,j-1), (i,j1)。只要该位置的高度低于当前(i,j)位置的高度就可以到达这里。
如果a[i-1][j] a[i][j]那么下一步可以到(i-1,j)。从(i,j)出发的最长路线长度为从(i-1,j)出发的最长路线长度再加1即dp[i][j] dp[i-1][j] 1。 如果a[i1][j] a[i][j]那么下一步可以到(i1,j)。从(i,j)出发的最长路线长度为从(i1,j)出发的最长路线长度再加1即dp[i][j] dp[i1][j] 1。 如果a[i][j-1] a[i][j]那么下一步可以到(i,j-1)。从(i,j)出发的最长路线长度为从(i,j-1)出发的最长路线长度再加1即dp[i][j] dp[i][j-1] 1。 如果a[i][j1] a[i][j]那么下一步可以到(i,j1)。从(i,j)出发的最长路线长度为从(i,j1)出发的最长路线长度再加1即dp[i][j] dp[i][j1] 1。 以上四种情况求最大值。 由于在求(i,j)时其上下左右四个位置的状态dp[i-1][j], dp[i1][j], dp[i][j-1], dp[i][j1]并不能确定都已经求出来了。因此可以通过记忆化递归的方法来求解状态。 设函数dfs(i, j)作用为求解状态dp[i][j]。如果dp[i][j]已经求出来了值大于0那么直接返回dp[i][j]。否则通过上述状态转移方程递归求解。
遍历所有的位置求出从每个位置出发的路线的最长长度求它们中的最大值即为该问题的结果。
【题解代码】
#include iostreamusing namespace std;const int N 105;int n, m, a[N][N], dp[N][N];
int mov[4][2] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};bool ok(int x, int y) {return x 0 x n y 0 y m;
}int dfs(int x, int y) { //返回从起点开始最多能滑几步(不包含起点)if (dp[x][y] ! 0)return dp[x][y];int maxn 0;for (int i 0; i 4; i ) {int dx x mov[i][0];int dy y mov[i][1];if (ok(dx, dy) a[dx][dy] a[x][y]) {maxn max(maxn, dfs(dx, dy));}}return dp[x][y] maxn 1;
}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]);int ans 0;for (int i 1; i n; i )for (int j 1; j m; j )ans max(ans, dfs(i, j));printf (%d, ans);return 0;
}
