1088:滑雪

keyword

動的計画法　C++

概要

100*100以下のボードがあり、各セルに高さが設定される。自分のセルより低い4近傍に移動できるとき、最も長いルートの長さを求める問題。
4近傍で極小(or 極大)の高さのセルから開始すれば素直なDP。
今考えると適当な点から幅優先して最大値-最小値で出そうな気もする。これだとソートが無い分オーダーが落ちるような。
readintも負の数を読み込めるようにしてみた。

inline int readint(){
    int ret = 0, x;
    bool plus = true;
    while(x=getchar(), !('0'<=x&&x<='9' || x=='-'));
    if(x=='-') plus = false;
    else ret = (x&15);
    while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);
    return plus?ret:-ret;
}

int main(){
    int n, m;
    int board[110][110];
    int dp[110][110];
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    int i, j, k;
    vector< pair<int, pair<int, int> > > where;

    REP(i,110)REP(j,110) board[i][j] = -1;
    REP(i,110)REP(j,110) dp[i][j] = -1;
    where.reserve(10010);

    n = readint();
    m = readint();
    REPONE(i,n)REPONE(j,m){
        board[i][j] = readint();
        where.PB(MP(board[i][j], MP(i,j)));
    }
    sort(ALL(where));

    EACH(where,it){
        int y = it->second.first,
            x = it->second.second;
        if(dp[y][x] == -1){
            dp[y][x] = 1;
        }
        REP(k,4){
            int ny = y + dy[k],
                nx = x + dx[k];
            if(board[ny][nx] > board[y][x]){
                dp[ny][nx] = max(dp[ny][nx], dp[y][x] + 1);
            }
        }
    }

    int ans = 0;
    REPONE(i,n)REPONE(j,m){
        ans = max(ans, dp[i][j]);
    }

    printf("%d\n", ans);
    return 0;
}