80求助,#1和#10没过

P1434 [SHOI2002] 滑雪

wangif424 @ 2022-07-27 17:36:11

#include<bits/stdc++.h>
using namespace std;
int r,c;
int book[101][101],ditu[101][101],dp[101][101],ans;
int main(){
    cin >> r >> c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> ditu[i][j];
            dp[i][j]=1;
        } 
    }
    for(int k=1;k<=r*c;k++){
        int mini=INT_MAX;
        int x=0;
        int y=0;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                if(book[i][j]==0&&mini>ditu[i][j]){
                    x=i;
                    y=j;
                    mini=ditu[i][j];
                }
            }
        }   
        //cout << x << " " << y << endl;
        book[x][y]=1;
        for(int i=1;i>=-1;i--){
            for(int j=1;j>=-1;j--){
                if(ditu[i+x][j+y]>ditu[x][y] && book[i+x][j+y]==0){
                    dp[i+x][j+y]=max(dp[i+x][j+y],dp[x][y]+1);
                }
            }
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ans=max(ans,dp[i][j]);
            //cout << dp[i][j] << " ";
        }
    //  cout << endl;
    }   
    cout << ans;
    return 0;
}

by dlydly @ 2022-07-27 17:38:16

吓得我还以为是P2573 [SCOI2012]滑雪


by UnyieldingTrilobite @ 2022-07-27 17:43:55

@wangif424 省流:你这个会走斜角,或者说八向滑


by zhaoqicheng2007 @ 2022-08-15 18:02:46

@wangif424 虽然没看懂,但是这个题肯定得用dfs记忆化搜索啊


|