[DP] 타워 문제
1340 단어 DP
아래의 숫자 피라미드를 관찰하다.프로그램이 가장 높은 지점에서 가장 큰 지점까지 임의로 끝난 경로를 찾아서, 경로가 숫자와 가장 큰 지점을 통과하도록 합니다.한 걸음 한 걸음 현재 점에서 왼쪽 아래 점까지 갈 수도 있고 오른쪽 아래 점까지 갈 수도 있다.
위의 예에서 13에서 8까지 26에서 15에서 24까지의 경로가 가장 큰 경로와 86을 만들었다.
Input
첫 번째 가방은 R(1≤R≤1000)을 포함하고 줄의 수를 나타낸다.
뒤에 있는 모든 행위의 숫자 피라미드의 특정 줄에 포함된 정수.
모든 공급된 정수는 마이너스이며 100보다 크지 않다.
Output
얻을 수 있는 가장 큰 합을 포함하는 단독 줄.
Sample Input 1
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
Sample Output 1
86
문제풀이
이 문제는 dp 입문 문제로 주요 목적은 이 과정을 익히는 것이다.
다음 예제를 주로 분석합니다.QAQ.
비록 이 예는 하나의 그림처럼 보이지만, 사실 이 문제는 도론의 지식을 필요로 하지 않는다.
먼저 샘플 입력을 통해 알 수 있듯이 우리가 입력한 데이터 더미는 다음과 같습니다.
(내가 갔는데 그림을 전송할 수가 없어...)
추이식: dp[i][j]=max(dp[i-1]j], dp[i-1][j-1])+a[i][j];
AC 코드
#include
using namespace std;
int n;
int a[1147][1147];
int dp[1147][1147];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}
dp[1][1] = a[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(dp[n][i], ans);
}
cout << ans;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.