到达(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; }