经典DP。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,map[150][150],cnt=0,step[150][150]; int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0}; struct pnt { int x,y,val; }p[10050]; bool cmp(pnt a,pnt b) { return a.val>b.val; } void addpnt(int x,int y,int z) { p[++cnt].x=x; p[cnt].y=y; p[cnt].val=z; } bool judge(int x,int y) { if ((x>=1) && (x<=n) && (y>=1) && (y<=m)) return true; return false; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { scanf("%d",&map[i][j]); addpnt(i,j,map[i][j]); } sort(p+1,p+cnt+1,cmp); for (int i=1;i<=cnt;i++) { for (int j=1;j<=4;j++) { if ((judge(p[i].x+dx[j],p[i].y+dy[j])) && (map[p[i].x][p[i].y]>map[p[i].x+dx[j]][p[i].y+dy[j]])) step[p[i].x+dx[j]][p[i].y+dy[j]]=max(step[p[i].x+dx[j]][p[i].y+dy[j]],step[p[i].x][p[i].y]+1); } } int ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) ans=max(ans,step[i][j]); printf("%d ",ans+1); return 0; }