poj-1088-滑雪
考察点 记忆化搜索
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[101][101];
int n,m;
int value[101][101];
int dfs(int x,int y)
{
if(dp[x][y]!=-1)
{
return dp[x][y];
}
int a=1,b=1,c=1,d=1;
if((x-1)>=0)
{
if(value[x][y]>value[x-1][y])
{
a=dfs(x-1,y)+1;
}
}
if((x+1)<n)
{
if(value[x][y]>value[x+1][y])
{
b=dfs(x+1,y)+1;
}
}
if((y-1)>=0)
{
if(value[x][y]>value[x][y-1])
{
c=dfs(x,y-1)+1;
}
}
if((y+1)<m)
{
if(value[x][y]>value[x][y+1])
{
d=dfs(x,y+1)+1;
}
}
int t=max(a,b);
t=max(t,c);
t=max(t,d);
dp[x][y]=t;
return t;//返回的是以i,j为开始最长的数字
}
int main()
{
cin>>n>>m;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>value[i][j];
int ma=-1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
ma=max(ma,dfs(i,j));
}
}
cout<<ma;
return 0;
}
