UVA Longest Run on a Snowboard(10285)
1989 단어 동적 기획
너에게 매트릭스를 하나 줄게. 스키장으로서 매트릭스의 각 단원 중의 수는 높이를 대표한다. 스키를 타는 사람은 높은 곳에서 낮은 곳까지만 미끄러질 수 있고 방향은 위, 아래, 왼쪽과 오른쪽만 미끄러질 수 있다. 스키를 타는 사람에게 가장 긴 몇 단원을 미끄러질 수 있느냐고 물었다.
문제 해결 방법:
이 문제는 본질적으로 행렬의 가장 긴 엄격한 연속 체감(또는 점증) 서열을 구하는 것이다. 즉, 서열의 원소는 서로 같을 수 없고 앞뒤가 서로 인접해야 한다.이 문제는 동적 기획 문제에 속하기 때문에 귀속에 사용해야 한다.
이미 찾은 체감 서열을 예로 들면 dp[i][j]를 설정하면 i, j점으로 구성된 서열이 얼마나 긴지 나타낸다. 이 값을 구하려면 위, 아래, 왼쪽과 오른쪽 네 방향만 비교하면 된다. board를 설정하면 제목이 주는 행렬을 표시하고 dfs(i, j)는 i, j점으로 구성된 서열의 길이를 구하면 얻을 수 있다.
만약board[i][j]>board[i-1][j]라면 dp[i][j]=dp[i-1][j]+1이고 dp[i-1][j]는 귀환으로 구할 수 있으며 상태 전이 방정식은 다음과 같다.
dp[i][j] = dfs( i-1 , j ) + 1;
그러나 아직 부족하다. board[i][j] 네 방향을 모두 한 번 계산하여 가장 큰 것을 취해야 하기 때문에 사용한다.
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
그리고 한 번 순환하여 최대 값을 꺼내 dp[i][j]에 부여하기 때문에 최종 상태 이동 방정식은 다음과 같다.
temp = max( temp, dfs( i + dx[k], j + dy[k] ) + 1 );
코드:
#include
#include
#include
#include
using namespace std;
int dp[105][105], board[105][105];
int dfs( int i, int j );
int main()
{
freopen( "test.txt", "r", stdin );
int T, m, n;
char name[50];
cin>>T;
while( T-- )
{
memset( dp, -1, sizeof( dp ) );
memset( board, 1, sizeof( board ) );
cin>>name>>m>>n;
for( int i = 1; i <= m; i++ )
{
for( int j = 1; j <= n; j++ )
{
cin>>board[i][j];
}
}
int ans = 0;
for( int i = 1; i <= m; i++ )
{
for( int j = 1; j <= n; j++ )
{
ans = max( ans, dfs( i, j ) );
}
}
cout<= 0 )
return dp[i][j];
int temp = 1;
for( int k = 0; k < 4; k++ )
{
if( board[i + dx[k]][j + dy[k]] < board[i][j] )
temp = max( temp, dfs( i + dx[k], j + dy[k] ) + 1 );
}
return (dp[i][j] = temp);
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
