求调

P1434 [SHOI2002] 滑雪

____HOW_TO_USE___ @ 2023-10-20 19:24:10

#include<iostream>
#include<algorithm>
using namespace std;
struct vnnbx{
    int x,y,t;
};
vnnbx a[10005];
int n,m,l=1,dp[105][105],ty=1,tyt[105][105],oct=-500000,df;
int yu[4][3]={{0,1},{1,0},{0,-1},{-1,0}};
bool comp(vnnbx aa,vnnbx bb){
    return aa.t<bb.t;
}
bool in(int fg,int fh,int nh,int mh){
    return fg>=1 && fg<=nh && fh>=1 && fh<=mh; 
}
int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;i<=m;j++){
            cin>>a[l].t;
            a[l].x=i;
            a[l].y=j;
            l++;
        }
    }
    sort(a+1,a+l,comp); 
    for(int i = 1;i<l;i++){
        if(a[i].t>oct){
            oct=a[i].t;
            df++;
            tyt[a[i].x][a[i].y]=df;
        } 
        else{
            tyt[a[i].x][a[i].y]=df;
        }
    }
    while(ty<l){
        int xx=a[ty].x,yy=a[ty].y;
        for(int i =0;i<4;i++){
            int xxx=xx+yu[i][0];
            int yyy=yy+yu[i][1];
            if(in(xxx,yyy,n,m) && tyt[xxx][yyy]<tyt[xx][yy]){
                dp[xx][yy]=max(dp[xx][yy],dp[xxx][yyy]+1);
            }
        }
        ty++;
    }
    int maxx=-132423213;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            maxx=max(maxx,dp[i][j]);
        }
    }
    cout<<maxx;
    return 0;
}

|