로곡 P1434 [SHOI2002] 스키(DP, 기억화 검색)

제목 설명

마이클은 스키를 좋아한다.이것은 결코 이상하지 않다. 왜냐하면 스키는 확실히 매우 자극적이기 때문이다.그러나 속도를 얻기 위해서는 미끄러운 구역이 아래로 기울어야 하며, 언덕 밑으로 미끄러지면 다시 언덕을 올라가거나 승강기가 너를 태우기를 기다려야 한다.마이클은 한 구역에서 가장 긴 미끄럼틀을 알고 싶어 한다.영역은 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 - 17 - 1 24 - 17 - 17 - 16 - 1 (24 24 24 에서 시작하여 1 1 1 1 에서 종료) 이 가능한 슬라이드입니다.물론 25-24-23-...3 － 2 － 1 25－24－23－...－3－2－1 25－24－23－...－3-2-1 길이.사실 이것이 가장 긴 것이다.

입력 출력 형식

입력 형식:
입력한 첫 번째 비헤이비어는 영역의 2D 배열의 행 수 R R R과 열 수 C C (1≤ R 1 ≤ R 1 ≤ R, C ≤ 100 C ≤ 100 C ≤ 100)을 나타냅니다.다음은 높이를 나타내는 R R R R 행으로, 각 행에 C C C 수가 있습니다(두 숫자 사이에 1칸으로 간격).
출력 형식:
출력 구역에서 가장 긴 미끄럼틀의 길이.

출력 샘플 가져오기

샘플 #1 입력:

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

사고의 방향

상태 전환 방정식을 쉽게 내놓을 수 있다. dp [i] [j] = m a x(dp [i i-1] [j] + 1, d p [i] [j] [j] [j] (i f d p [i] [j]] = m a x (dp [i i i i i i 1] [j]] dp[i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] dp[j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [jdp[i][j]>dp[i-31][j])
d p [ i ] [ j ] = m a x ( d p [ i + 1 ] [ j ] + 1 , d p [ i ] [ j ]    ( i f   d p [ i ] [ j ] > d p [ i + 1 ] [ j ] ) dp[i][j]=max(dp[i+1][j]+1,dp[i][j]\\(if\dp[i][j]>dp[i+1][j]) dp[i][j]=max(dp[i+1][j]+1,dp[i][j]  (if dp[i][j]>dp[i+1][j])
d p [ i ] [ j ] = m a x ( d p [ i ] [ j − 1 ] + 1 , d p [ i ] [ j ]    ( i f   d p [ i ] [ j ] > d p [ i ] [ j − 1 ] ) dp[i][j]=max(dp[i][j-1]+1,dp[i][j]\\(if\dp[i][j]>dp[i][j-1]) dp[i][j]=max(dp[i][j−1]+1,dp[i][j]  (if dp[i][j]>dp[i][j−1])
d p [ i ] [ j ] = m a x ( d p [ i ] [ j + 1 ] + 1 , d p [ i ] [ j ]    ( i f   d p [ i ] [ j ] > d p [ i ] [ j + 1 ] ) dp[i][j]=max(dp[i][j+1]+1,dp[i][j]\\(if\dp[i][j]>dp[i][j+1]) dp[i][j]=max(dp[i][j+1]+1,dp[i][j]  (if dp[i][j]>dp[i][j+1])
그러나 d p [ii-1] [j], d p [i+1] [j], d p [i] [j] [j ii] [j] [j], d p [i+1] [i+1] [j], dp[i+1] [j], d p [i] [i] [i] [j 1] [j] [i] [i] [i] [j] [j], dp[i+1] [j], dp[i+1] [j], dp[i] [j[j[i] [j[j], dp[i] [j+1] [j+1] [j+1]의 선형 값은 일반적인 dp[i] [j+1] dp[j+1의 수치를 구할 수 없으므로 dp[i]의 일반적인 dp[j+1] 수치를 구하지 못하므로 모든 기억을 검색하고, 이렇게 하면 상술한 네 가지 상태의 값을 획득한 다음에 dp를 진행하면 된다
2차원 지도를 차원을 낮추고 선형 dp를 진행할 수도 있습니다. 구체적인 방법은 Dalao 블로그를 보십시오.https://sparky.blog.luogu.org/solution-p1434

AC 코드

/*************************************************************************

	 > Author: WZY
	 > School: HPU
	 > Created Time:   2019-02-06 20:45:27
	 
************************************************************************/
#include 
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn=1e3+10;
const int mod=1e9+7;
using namespace std;
int a[maxn][maxn];
int dp[maxn][maxn];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m;
int dfs(int x,int y)
{
	if(dp[x][y])
		return dp[x][y];
	int _=0;
	for(int i=0;i<4;i++)
	{
		int dx=x+dir[i][0];
		int dy=y+dir[i][1];
		if(dx<=n&&dx>0&&dy<=m&&dy>0&&a[x][y]>a[dx][dy])
			_=max(dfs(dx,dy)+1,_);
	}
	dp[x][y]=max(_,dp[x][y]);
	return dp[x][y];
}
int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	ms(dp,0);
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,dfs(i,j));
	cout<<ans+1<<endl;
	return 0;
}