joj2511

2511: Number triangle

Result
TIME Limit
MEMORY Limit
Run Times
AC Times
JUDGE
1s
65536K
427
217
Standard

        5
      3   4
    8   1   2
  5   4   3   6
2   1   7   9   8

A number trangle is composed of N(N<=100) line numbers, the i-th line contains i positive integers(<=100). A chess can walk from the top line of the triangle to the bottom line. Suppose the chess is on the k-th number of one line, then it can only move to the k-th number or the (k+1)-th number of the line below in one step. Find a path from the top to the bottom, which can maximize the sum of the integers on the path.

Input

There are multiple test cases.For each test case, there's an integer N representing the size of the triangle, followed by N lines of positive intergers, the first line has 1 integer, next has two integers... the Nth line has N integers.

Output

The maximum sum of the integers on the path.

Sample Input

Sample Output

16
12

Developed by skywind, SIYEE
#include #include using namespace std; int a[100+3][100+3]; int s[100+3][100+3]; int main() { int n; while(scanf("%d",&n)==1) { for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); } } s[1][1]=a[1][1]; for(int i=2;i<=n;i++) { s[i][1]=s[i-1][1]+a[i][1]; for(int j=2;j<=i;j++) { s[i][j]=max(s[i-1][j],s[i-1][j-1])+a[i][j]; } } int maxt=-1; for(int i=1;i<=n;i++) { if(s[n][i]>maxt) { maxt=s[n][i]; } } printf("%d",maxt); } return 0; }
이것은 전형적인 동적 기획의 제목이다. 관건은 표현식 s[i][j]=max(s[i-1][j-1], s[i-1][j])+a[i][j]를 찾는 것이다.정점에서 i행 j 번째 점까지의 최대치를 나타냅니다...

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

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

cocos2d Lua 학습(一)

ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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