nefu 18 滑雪

http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=18

題意： 找一條從高到低的最長的路的長度；

思路：記憶化搜尋，但是不知道在那個地方開始或者結束，是以所有的點都走一遍：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn = 100 + 10;
int dp[maxn][maxn];
int a[maxn][maxn];
int derict[][2] =
{
	-1,0,
	1,0,
	0,1,
	0,-1
};
int n, m;
int dfs(int x, int y)
{
	if (dp[x][y] != -1)
		return dp[x][y];
	int maxs = 0;
	for (int i = 0; i < 4; i++)
	{
		int xx = x + derict[i][0], yy = y + derict[i][1];
		if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[x][y] > a[xx][yy])
		{
			maxs = max(maxs, dfs(xx, yy));
		}
	}
	return dp[x][y] = maxs + 1;
}
int main()
{
	
	while (~scanf("%d%d", &n, &m))
	{
		memset(dp, -1, sizeof(dp));
		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);
		}
		int ans = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				ans = max(ans, dp[i][j]);
			}
		}
		cout << ans << endl;
	}
	return 0;
}