当前位置: 代码迷 >> 综合 >> POJ 1088 滑雪(最长下降子序列)
  详细解决方案

POJ 1088 滑雪(最长下降子序列)

热度:32   发布时间:2023-12-08 11:23:08.0

题目链接:POJ 1088

题意:

给一个二维数组,每个数组元素是一个整数表示高度,每次从一个点可以上下左右四个方向移动,但是必须是高度下降方向,问最长的下降长度是多少?

例如:25->24->23->......->3->2->1,长度是25.

分析:

求最长下降子序列问题。使用DP+递归。

DP状态转移方程://DP[i][j]表示从(i,j)位置出发的最长下降子序列

DP[i][j]=max(DP[x][y])+1;其中(x,y)是(i,j)上下左右四个方向上的合法下标

注意点:

  • 记忆化搜索,避免重复计算
  • x,y合法性判断
  • return时应+1(本身一个元素)


CODE:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn = 105;
int height[maxn][maxn], dp[maxn][maxn];
//height[i][j]表示二维数组中下标为(i,j)的高度,dp[i][j]是相应最长下降子序列
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int x, y, r, c;int DP(int row, int col)
{if (dp[row][col] > 0) return dp[row][col];//已经计算过了int tmpmax = 0;//这里只能初始化为0,而不能是-1for (int i = 0;i < 4;i++)//4个方向查找最大值{x = row + dir[i][0];y = col + dir[i][1];if (x < 0 || y < 0 || x >= r || y >= c || height[x][y] >= height[row][col]) continue;//下标越界或者高度不满足下降条件tmpmax = max(tmpmax, DP(x, y));//取四个方向中的最大值}return tmpmax + 1;//结果要算上(row,col)本身这一个元素
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifwhile (cin >> r >> c){memset(dp, -1, sizeof(dp));for (int i = 0;i < r;i++)for (int j = 0;j < c;j++)cin >> height[i][j];int ans = -1;for (int i = 0;i < r;i++){for (int j = 0;j < r;j++){dp[i][j] = DP(i, j);ans = max(ans, dp[i][j]);}	}cout << ans << endl;}return 0;
}