60分!求助大佬

P1434 [SHOI2002] 滑雪

小超手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

似乎是最长路径不一定从最高点开始


|