POJ 1088(DP 역귀환법 + 순환법)

스키를 타다
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 93021
 
Accepted: 35199
Description
마이클이 스키를 좋아한다는 것은 이상하지 않다. 왜냐하면 스키는 확실히 자극적이기 때문이다.그러나 속도를 얻기 위해서는 미끄러운 구역이 아래로 기울어야 하며, 언덕 밑으로 미끄러지면 다시 언덕을 올라가거나 승강기가 너를 태우기를 기다려야 한다.마이클은 한 구역에서 가장 긴 언덕을 싣는 것을 알고 싶어 한다.영역은 2차원 그룹으로 표시됩니다.배열의 각 숫자는 점의 높이를 나타냅니다.다음은 하나의 예이다

 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

한 사람이 어떤 점에서 상하좌우로 미끄러져 네 점 중 하나와 인접할 수 있으며, 높이가 줄어들 때만 된다.위의 예에서 활주할 수 있는 미끄럼틀은 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

문제 풀이 과정:
세 번째 주간 대회의 H 문항으로, 당시 첫 반응은 BFS로 하고 점마다 찾아보는 것이었으나 TLE가 될 수 있다는 생각이 들었고, 이후 실천에서도 이를 입증했다.
제목 힌트는 DP입니다. 제 이해에서 DP는 두 가지 방식일 뿐입니다. 귀속 or 추이
반복 알고리즘:

#include 
#include 
#include 
#include 
#define N 101
using namespace std;
int map[N][N],len[N][N];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int r,c;
int dp(int i,int j)
{
    if(len[i][j]!=0)return len[i][j];
    int maxx=0,s;
    for(int t=0;t<4;t++)
      {
          int temx=i+dir[t][0],temy=j+dir[t][1];
          if(temx>=0&&temx=0&&temymaxx)	maxx=s;//      max   ，         max{}  
          }
           
      }
    len[i][j]=maxx+1;
    return maxx+1;
}
 
int main()
{
    while(~scanf("%d%d",&r,&c))
    {
        int mx=-1;
        memset(len,0,sizeof(len));
        for(int i=0;imx)	mx=len[i][j];
      		}
      printf("%d
",mx);   
    }
    return 0; 
}

추출 알고리즘:
이전에 만든 최장 합법 서열(hoj 10179):
k 개의 정수 A[1], A[2]가 있습니다.A[k], 앞으로 나아가서 몇 개의 수를 골라서 각 뒤의 수가 앞의 수보다 크거나 같게 해야 합니다.예를 들어 시리즈 1, 4, 2, 5, 2, 3에 대해 1, 2, 3을 선택하는 것은 합법적이지만 4, 2, 3을 선택하는 것은 합법적이지 않다.
이것은 또한 고전적인 점차적 DP이기도 하지만 차이점은 다음과 같다.
최대 합법 시퀀스 상태 전환 방정식:
dp(i,A[i])=max{dp(i+1,A[i+1]),dp(i+1,A[i])}+1;
그것은 점차적인 형식으로 쓰여졌다.
이 문제는 상태 이동 방정식이다.
dp(i,j,H[i][j])=
max{dp(i+1,j,H[i+1][j]),dp(i-1,j,H[i-1][j],dp(i,j+1,H[i][j+1],dp(i,j-1,H[i][j-1]} + 1;
그림의 구조에 따라 직접 추론하면 2차원 형식이 될 것이다. 그러면 나는 추론을 쓰지 않을 것이다.따라서 모든 점을 H 내림차순으로 배열하면 1차원 추이식으로 바뀐다.
코드는 다음과 같습니다.

#include
#include
#include
using namespace std;
int r,c,dir[4][2]={0,1,0,-1,1,0,-1,0},step[101][101],H[101][101];
struct dot{
	int x;int y;int h;
}map[10001];
bool judge(int rr,int cc){
	if(rr>=0&&cc>=0&&rrv.h;// h     
}
int main()
{
	scanf("%d%d",&r,&c);
	int height;
	for(int i=0;istep[temp.x][temp.y])
					step[temp.x][temp.y]=step[xx][yy]+1;
			}
		}	
	}
	for(int i=0;i

총괄:DP는 사유가 매우 중요하기 때문에 아직은 발을 파야 하고 자신의 자세 수준을 향상시키려고 노력해야 한다.