60分求助

P1434 [SHOI2002] 滑雪

Ohhhhhh321 @ 2021-11-30 16:36:27


using namespace std;
const int inf=0x3f3f3f3f;
int next[4][2]={
0,1,1,0,0,-1,-1,0};
int r,c;
struct ac{
    int high,step;
}dp[105][10];
int temp1=0,temp2=0;
int ac1(int x,int y){
    if(dp[x][y].step!=inf)return dp[x][y].step;
    for(int i=0;i<4;i++){
        if(x+next[i][0]>=0&&y+next[i][1]>=0&&dp[x+next[i][0]][y+next[i][1]].high<dp[x][y].high&&x+next[i][0]<r&&y+next[i][1]<c){
        temp2=dp[x][y].step;
        if(temp2!=inf){
            dp[x][y].step=max(ac1(x+next[i][0],y+next[i][1])+1,temp2);
        }
        else {
        dp[x][y].step=ac1(x+next[i][0],y+next[i][1])+1;}
        temp1=1;}
    }
    if(temp1==1){
        temp1=0;
        return dp[x][y].step;
    }
    else {
        dp[x][y].step=1;
        return 1;
    }
}
int main(){

    scanf("%d%d",&r,&c);
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
        scanf("%d",&dp[i][j].high);
        dp[i][j].step=inf;
    }}
    int ans=1;
    for(int y=0;y<r;y++){
    for(int u=0;u<c;u++){
    ans=max(ans,ac1(y,u));
//  ans=ac1(y,u);
//  printf("%d ",dp[y][u].step);
    }
//  printf("\n");
    }
    printf("%d",ans);
    return 0;   
}

|