DP 연습문제: POJ-스키(본 적 없는 스트리밍 순서)

제목 설명
마이클은 스키를 좋아한다.이것은 결코 이상하지 않다. 왜냐하면 스키는 확실히 매우 자극적이기 때문이다.그러나 속도를 얻기 위해서는 미끄러운 구역이 아래로 기울어야 하며, 언덕 밑으로 미끄러지면 다시 언덕을 올라가거나 승강기가 너를 태우기를 기다려야 한다.마이클은 한 구역에서 가장 긴 미끄럼틀을 알고 싶어 한다.영역은 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(24부터 시작하여 1에서 끝난다)이다.물론 25-24-23―3―2―1이 더 길다.사실 이것이 가장 긴 것이다.
입력 출력 형식
입력 형식: 입력한 첫 번째 비헤이비어는 영역의 2D 배열을 나타내는 행 수 R과 열 수 C(1≤R, C≤100)를 나타냅니다.다음은 높이를 나타내는 R 행으로, 각 행에는 C 개의 수가 있습니다(두 숫자 사이에는 1 공백으로 간격을 두었음).
출력 형식: 출력 영역에서 가장 긴 미끄럼틀의 길이입니다.
출력 샘플 가져오기
샘플 입력 1:5 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 출력 샘플 1:25
샘플 2:2 2 3 1 4 2 입력
출력 예제 2:3
POJ의 이전 고전적인 dp문제도 mooc에서 동적 기획을 강의한 예제이다.이 문제는 사실 미로 유형의 dp문제에 속한다. 나는 이런 유형의 문제는 검색이든 dp든 모두 간단할 것이라고 생각한다. 왜냐하면 상태는 dp[i][j]표시점(i, j)의 어떤 상태로 설정된 것이 틀림없기 때문이다.그럼 이 문제, dp[i][j]는 당연히 점(i, j)이 미끄러질 수 있는 최대 길이의 값을 나타낸다!
이 문제의 상태 이동도 간단하다. dp[i][j]=max(dp[i-1][j]+1, dp[i+1][j]+1, dp[i][j-1]+1, dp[i][j-1]+1, dp[i][j+1]+1, dp[i][j]).그 중에서 주의: 네 방향의 점 좌표값은 반드시 합법적이어야 하고 점의 높이는 (i, j)의 높이보다 작아야 이 상태 이동 방정식 안으로 대체할 수 있다!이것은 모두 약간의 세부 사항이니 문제가 되지 않는다.
그럼 코드를 쓰기 시작하려고 할 때 또 문제가 생겼어요.dp의 경계와 역행 순서는 무엇입니까?이것은 명확하지 않아서 dp는 쓸 수 없다.오오, 생각한 결과 각 점의 dp값은 전후 좌우 네 방향이고 하이라이트가 (i, j)보다 낮은 점의 dp값으로 추정되기 때문에 dp[i][j]를 구하기 전에 하이라이트가 (i, j)보다 낮은 점의 dp값을 구해야 한다!
따라서 반복 순서는 점의 높이 순서와 관계가 있기 때문에 나는 하나의 수조 a를 만들고 높이를 낮은 것에서 높은 것으로 정렬한 다음에 그들의 점의 dp값을 순서대로 계산하고 마지막에 가장 큰 dp값을 찾아 돌아오면 된다!
참조 코드: (코드는 아이디어만 나타내고 OJ 평가를 하지 않음)

/*
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

  ：25


2 2
3 1
4 2

  ：3 
*/
#include
#include
#include
using namespace std;

const int maxn = 100;
struct Node{
	int x;
	int y;
	int height;
};
Node a[maxn];
int m, n;
int len;
int map[maxn][maxn];
int dp[maxn][maxn];

bool cmp(Node x, Node y)
{
	return x.height < y.height ? true : false;
}

int DP()
{
	int i = 0, j = 0;
	int h = 0;
	int max_res = 0;
	// a                
	for(int k = 1;k < len;k++)
	{
		i = a[k].x;
		j = a[k].y;
		h = a[k].height;
		if(i + 1 <= m && map[i + 1][j] < h)
			dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1);
		if(i - 1 >= 1 && map[i - 1][j] < h)
			dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);
		if(j + 1 <= m && map[i][j + 1] < h)
			dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1);
		if(j - 1 >= 1 && map[i][j - 1] < h)
			dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1);
		if(dp[i][j] > max_res)
			max_res = dp[i][j];
	}
	//  dp  
	cout << "dp  ：" << endl;
	for(int i = 1;i <= m;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	} 
	return max_res;
}

void Init()
{
	for(int i = 1;i <= m;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			dp[i][j] = 1;
		}
	}
}

int main()
{
	cin >> m >> n;
	len = 1;
	for(int i = 1;i <= m;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			cin >> map[i][j];
			a[len].x = i;
			a[len].y = j;
			a[len].height = map[i][j];
			len++;
		}
	}
	sort(a + 1, a + len, cmp);	//dp             
	Init(); 					//    ，    1 					
	cout << DP() << endl;
	return 0;
}