POJ 1088 滑雪 C++版

发表于 更新于

题目链接：http://poj.org/problem?id=1088

DP初学者的好题，题意也简单，找2维数组，最长降序数列。

DP解题的经典问题，利用记忆搜索，也是我们平常的递归运算。

讲一下思路，递归4方向搜索，求最大的数，我利用的一个方向数组来完成四个方向的！

其中，两个问题拦住了我的AC，

第一个先开始，纯利用递归，导致重复计算量过大，TLE了，我们观察下其实每个点开始的最长降序数列的长度都是固定的，我们利用dp数组储存每个点的信息，可以避免重复计算，

第二个是，我在dfs函数中先开始，判断的条件是

1
2
3
if(map[m][n]>0)


1
2
3
4
if(m>=1&&m;<=c&&n;>=1&&n;<=r)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/***************************************
Problem: 1088		User: awq123
Memory: 336K		Time: 63MS
Language: C++		Result: Accepted
***************************************/ 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int r,c,map[105][105],dp[105][105],step[8]={1,0,0,1,-1,0,0,-1};

int dfs(int x,int y)
{
	if(dp[x][y]!=0)
		return dp[x][y];
	int max=1,temp;
	for(int i=0;i<8;i+=2)
	{
		int m=x+step[i],n=y+step[i+1];
		if(m>=1&&m;<=c&&n;>=1&&n;<=r)
			if(map[m][n]<map[x][y])
			{
				temp=dfs(m,n)+1;
				if(temp>max)
					max=temp;
			}
	}
	return max;
}

int main()
{
	int i,j,max=1;
	memset(map,0,sizeof(map));
	memset(dp,0,sizeof(dp));
	cin>>r>>c;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
			cin>>map[j][i];
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			dp[j][i]=dfs(j,i);
			if(dp[j][i]>max)
				max=dp[j][i];
		}
	cout<<max<<endl;
}