2015年1月10日 星期六

2014/01/10 vijos P1011 清帝之惑之顺治

/*
    按照高度的順序來更新
    北軟 有出現過類似的題目
*/
// https://vijos.org/p/1011
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef pair<int, int> xy;
#define x first
#define y second

int R, C;
int DP[600][600], H[600][600];

vector<xy> v;
bool cmp(xy t1, xy t2){ return H[t1.x][t1.y] > H[t2.x][t2.y]; }

int vx[] = {-1, 0, 1, 0};
int vy[] = {0, -1, 0, 1};

int main()
{
    scanf("%d %d", &R, &C);

    for(int Ri = 0; Ri < R; Ri++)
        for(int Ci = 0; Ci < C; Ci++)
        {
            scanf("%d", &H[Ri][Ci]);
            DP[Ri][Ci] = 1;
            v.push_back(xy(Ri, Ci) );
        }

    sort(v.begin(), v.end(), cmp);

    int Ans = 0;

    for(int vi = 0; vi < v.size(); vi++)
    {
        int x = v[vi].x;
        int y = v[vi].y;

        for(int i = 0; i < 4; i++)
        {
            int nx = x+vx[i];
            int ny = y+vy[i];

            if( nx < 0 || nx >= R ) continue;
            if( ny < 0 || ny >= C ) continue;

            if( H[nx][ny] > H[x][y] )
                DP[x][y] = max(DP[x][y], DP[nx][ny]+1);

            Ans = max(Ans, DP[x][y]);
        }
    }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言