DP 동적 계획 문제 F 1006 수 탑 문제
간단 한 제목: 하나의 수 탑 을 제시 하고 꼭대기 층 에서 끝까지 가면 한 걸음 에 인접 한 결점 까지 만 갈 수 있 고 지나 간 결점 의 최대 숫자의 합 을 구한다.
문제 풀이 사고의 형성 과정: 위 에서 아래로, 마지막 두 번 째 층 부터 모든 결점 은 두 가지 선택 이 있다. 자신의 수 에 왼쪽 아들 이나 자신의 수 에 오른쪽 아들 을 더 하면 이들 의 수 는 최대 치 를 구하 고 최대 치 는 바로 이 결점 의 최대 치 이다.이 방법 에 따라 꼴찌 에서 두 번 째 로 맨 꼭대기 까지 차례로 옮 겨 다 닌 다.이때 가장 꼭대기 층 의 수 는 바로 꼭대기 층 에서 끝까지 가 는 숫자의 합 의 최대 치 이다.
소감: 비교적 간단 한 DP 문제 입 니 다. 자신 이 테스트 할 때 debug 를 한참 동안 했 습 니 다. 디 테 일 에 주의 하 세 요!
코드:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[20000][20000];
int num;
void dp()
{
for(int i=num-2;i>=0;--i)
for(int j=0;j<i+1;++j)
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
}
int main()
{
//freopen("1.txt","r",stdin);
int n;
scanf("%d",&n);
while(n--)
{
scanf("%d",&num);
for(int i=0;i<num;++i)
for(int j=0;j<i+1;++j)
scanf("%d",&a[i][j]);
dp();
printf("%d
",a[0][0]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
