로곡 P1216 디지털 삼각형(dp)
2614 단어 DP
프로그램이 가장 높은 지점에서 가장 큰 지점까지 임의로 끝난 경로를 찾아서, 경로가 숫자와 가장 큰 지점을 통과하도록 합니다.한 걸음 한 걸음 왼쪽 아래까지 갈 수도 있고 오른쪽 아래까지 갈 수도 있다.
입력 출력 형식 입력 형식: 첫 번째 패키지는 R(1<=R<=1000)을 포함하고 줄의 수를 나타낸다.
뒤에 있는 모든 행위의 숫자 피라미드의 특정 줄에 포함된 정수.
모든 공급된 정수는 마이너스이며 100보다 크지 않다.
출력 형식: 얻을 수 있는 최대의 합을 포함하는 단독 줄입니다.
입력 출력 예제 입력 예제 #1:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
샘플 내보내기 #1:
30
이 문제는 많은 문법이 있는데, 여기에는 단지 한 가지만 소개한다...주요한 사고방식은 아래에서 위로 미루는 것이다. 현재 n-1층을 가정하면 위로 n-2층은 n-1층의 두 수에 의해 결정되고 어느 것을 크게 더하고 어느 것을 바꾸며 n-2층의 값을 바꾸면 1번 노드까지 계속 바뀐다.부호를 붙이다
#include
#include
#include
#include
using namespace std;
int n;
int a[1005][1005];
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
scanf("%d",&a[i][j]);
}
}
for(i=n-1;i>=1;i--){
for(j=1;j<=i;j++){
int p1=a[i][j]+a[i+1][j];
int p2=a[i][j]+a[i+1][j+1];
a[i][j]=max(p1,p2);//
}
}
printf("%d",a[1][1]);
return 0;
}
총괄: dp문제는 상태 이동이 중요하다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.