到达(i,j)点的长度=max(周围比它大的点的数目+1);
而枚举的时候,需要按照一定的顺序,这样避免遗漏;
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 601
int ma[maxn][maxn],d[maxn][maxn];
struct m{
int x,y;//坐标
int hight;//高度
}g[251000];//将一个点的信息存到g中
bool compare(m i,m j)
{
return i.hight>j.hight;
}
int main()
{
int r,c,ans=0,k=0;
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++){
cin>>ma[i][j];
g[++k].x=i,g[k].y=j;
g[k].hight=ma[i][j];
d[i][j]=1;//初始化dp
}
sort(g+1,g+1+k,compare);//按照从小到大排序
for(int i=1;i<=k;i++)
{
int w=g[i].x,u=g[i].y;
if(ma[w][u]>ma[w-1][u]&&(w-1)>0)
{
d[w-1][u]=max(d[w][u]+1,d[w-1][u]);
}
if(ma[w][u]>ma[w+1][u]&&w+1<=r)
{
d[w+1][u]=max(d[w][u]+1,d[w+1][u]);
}
if(ma[w][u]>ma[w][u-1]&&u-1>0)
{
d[w][u-1]=max(d[w][u]+1,d[w][u-1]);
}
if(ma[w][u]>ma[w][u+1]&&u+1<=c)
{
d[w][u+1]=max(d[w][u]+1,d[w][u+1]);
}
}
for(int i=1;i<=r;i++)//枚举取最值;
for(int j=1;j<=c;j++)
ans=max(ans,d[i][j]);
cout<<ans;
return 0;
}
京公网安备 11010502036488号