POJ-1088 스키(기억화 검색, dp)

스키 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 Accepted: 32289 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
동적 기획의 제목 상태 이동 방정식: dp[x][y]=max{네 방향의 값} 사실 이 제목은 기억화 검색과 동적 기획의 관계와 관련이 있다.나는 동태계획을 처음 배웠는데 이런 제목을 알아차리고 뻔뻔스럽게 정리했다. if(dp[x][y])returndp[x][y];이 문장은 DFS 함수에서 매우 중요하고 기억화 검색의 원천이다.http://blog.csdn.net/dacc123/article/details/50317371이 블로그에서 나는 이 제목과 관련이 있다고 생각한다. 마찬가지로 깊이 있게 우선적으로 검색하는 형식으로 동적 계획을 완성했다.차이점은 이것이 한 집합면에서 최대치를 찾았고 다른 하나는 직접 계승되었다는 것이다.앞으로도 계속 관심을 가지고 총결산을 해야 한다.

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
int n,m;
int a[105][105];
int dp[105][105];//                 
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool tag;
int maxin;
int DFS(int x,int y)
{
    if(dp[x][y])
        return dp[x][y];
    int res=0;
    for(int i=0;i<4;i++)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(xx<0||xx>n-1||yy<0||yy>m-1)
            continue;
        if(a[xx][yy]<a[x][y])
            res=max(res,DFS(xx,yy));
    }
    dp[x][y]=res+1;
    return dp[x][y];


}
int main()
{
    int ans;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                scanf("%d",&a[i][j]);
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {

                if(ans<DFS(i,j))
                    ans=DFS(i,j);

            }
        }
        printf("%d
",ans);

    }
    return 0;
}