POJ 1088 스키(dp)

원제 설명: 스키 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 88680 Accepted: 33272 Description
마이클이 스키를 좋아한다는 것은 이상하지 않다. 왜냐하면 스키는 확실히 자극적이기 때문이다.그러나 속도를 얻기 위해서는 미끄러운 구역이 아래로 기울어야 하며, 언덕 밑으로 미끄러지면 다시 언덕을 올라가거나 승강기가 너를 태우기를 기다려야 한다.마이클은 한 구역에서 가장 긴 언덕을 싣는 것을 알고 싶어 한다.영역은 2차원 그룹으로 표시됩니다.배열의 각 숫자는 점의 높이를 나타냅니다.다음 예는 하나, 둘, 셋, 넷, 다섯.
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
한 사람이 어떤 점에서 상하좌우로 미끄러져 네 점 중 하나와 인접할 수 있으며, 높이가 줄어들 때만 된다.위의 예에서 활주할 수 있는 미끄럼틀은 24-17-16-1이다.그럼요. 25-24-23-... -3-2-1이 더 길어요.사실 이것이 가장 긴 것이다.Input
입력한 첫 번째 행은 영역의 행 수 R과 열 수 C(1 <= R, C <= 100)를 나타냅니다.다음은 R줄입니다. 줄마다 C개의 정수가 있는데 높이 h, 0<=h<=10000을 대표합니다.Output
가장 긴 영역의 길이를 내보냅니다.Sample Input 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
Sample Output 25
분석: 첫 번째 반응 기억말 검색, 가장 높은 것부터 검색, 한 번 기억하고 한 번 검색, ac, 이왕 이렇게 된 이상 dp도 틀림없이 될 거야. 그래서 dp를 했어. 반대로 하고 가장 낮은 것부터 다시 검색하면 돼. 그래서 미리 순서를 정해야 돼.
dp[i][j]: 그것보다 낮은 위치에서 여기까지 연결된 가장 긴 개수 전이 방정식: dp[i][j]=max(주위 네 칸의 값)
코드:

#include "stdio.h"
#include "algorithm"
using namespace std;
struct node
{
    int x,y,h;
};
node hei[10000+5];
int height[100+5][100+5];
int dp[100+5][100+5];
int r,c;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool cmp(node a,node b)
{
    return a.h<b.h;
}
int main()
{
    scanf("%d%d",&r,&c);
    int cnt=0;
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            scanf("%d",&hei[cnt].h);
            height[i][j]=hei[cnt].h;
            dp[i][j]=1;
            hei[cnt].x=i;
            hei[cnt++].y=j;
        }

    }
    sort(hei,hei+r*c,cmp);
    int res=0;
    for (int i = 0; i < r*c; ++i)
    {

        int x=hei[i].x,y=hei[i].y;
        int tmp=0;
        for (int j = 0; j < 4; ++j)
        {
            int xx=x+dx[j],yy=y+dy[j];
            if(xx<0||xx>=r||yy<0||yy>=c) continue;
            if(height[x][y]>height[xx][yy]){
                tmp=dp[xx][yy]+1;
                if(tmp>dp[x][y]){
                    dp[x][y]=tmp;
                }
            }
        }
        if(dp[x][y]>res){
            res=dp[x][y];
        }
    }
    printf("%d
",res);
    return 0;
}