小超手123 @ 2022-05-11 19:33:37
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[110][110];
int walk[10][10]={{1,0},{0,1},{-1,0},{0,-1}};
int dp[110][110];
struct node{
int x,y;
int h;
}p[100101];
int cnt=0;
bool cmp(node aa,node bb){
return aa.h>bb.h;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
cnt++;
p[cnt].x=i;
p[cnt].y=j;
p[cnt].h=a[i][j];
}
}
sort(p+1,p+cnt+1,cmp);
dp[p[1].x][p[1].y]=1;
for(int i=2;i<=cnt;i++){
int xx=p[i].x,yy=p[i].y;
int hh=p[i].h;
for(int j=0;j<4;j++){
int dx=xx+walk[j][0],dy=yy+walk[j][1];
if(a[dx][dy]>hh){
dp[xx][yy]=max(dp[dx][dy]+1,dp[xx][yy]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
return 0;
}
by Q9_KKK @ 2022-05-15 22:50:24
似乎是最长路径不一定从最高点开始