D e s c r i p t i o n Description Description

모두들 일과 휴식을 함께 하자고 한다. A y u m i, M i t s u h i k o, G e n t a Ayumi, Mitsuhiko, Genta Ayumi, Mitsuhiko, Genta가 네모를 그리고 운동하러 나간다!그들은 공터에 와서 N개의 연속된 네모를 그렸고 각 네모마다 무작위로 숫자를 채웠다. 모두들 첫 번째 칸부터 시작하여 매번 현재 칸의 수를 초과하지 않고 뒤로 뛸 수 있다. 모두들 이 경기를 시작하여 누가 마지막 칸까지 뛰는 걸음수가 가장 적은지 보았다.리더인 G e n t a Genta Genta는 분명히 승리를 노렸기 때문에 Co n a n Conan Conan에 전화를 걸어 도움을 요청했지만 Co n a n Conan Conan이 게임을 하고 있어서 도움을 요청했다.

I n p u t Input Input

첫 번째 행에 그림의 칸 수를 나타내는 정수 N N N 을 입력합니다.두 번째 행에는 각 칸의 수 a i ai ai를 나타내는 N 정수가 포함됩니다.

O u t p u t Output Output

한 줄을 출력합니다. 점프의 최소 걸음 수를 표시합니다.

S a m p l e I n p u t Sample Input SampleInput

5
2 3 1 1 1

S a m p l e O u t p u t Sample Output SampleOutput

E x p l a i n Explain Explain

40%의 데이터가 N<=10, ai<=10을 충족합니다.100% 데이터에는 N<=5000, ai<=1000이 충족됩니다.

T r a i n Train Train O f Of Of T h o u g h t Thought Thought

f[j] f[j] f[j]를 설정하여 jj 이 칸에 필요한 최소 걸음수 동적 이동 방정식은 f[j] = m in(f[i] + 1, f[j]) f[j] =min(f[i] +1, f[j]) f[j] =min(f[j] =min(f[i] +1, f[j])

C o d e Code Code

#include
#include
#include
#include
using namespace std;
int f[5005],a[5005],n;
int main()
{
	memset(f,0x7f,sizeof(f));
	scanf("%d",&n);
	for (int i=1; i<=n; ++i)
	 scanf("%d",&a[i]);
	f[1]=0;
	for (int i=1; i<=n; ++i)//      
	 for (int j=i+1; j<=i+a[i]; ++j)//        
	  f[j]=min(f[i]+1,f[j]);
	printf("%d",f[n]);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다