USACO-Section 1.5 Number Triangles(DP)

묘사

아래의 숫자 피라미드를 관찰하다.
프로그램이 가장 높은 지점에서 가장 큰 지점까지 임의로 끝난 경로를 찾아서, 경로가 숫자와 가장 큰 지점을 통과하도록 합니다.한 걸음 한 걸음 왼쪽 아래까지 갈 수도 있고 오른쪽 아래까지 갈 수도 있다.

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

위의 예에서 7에서 3에서 8에서 7에서 5까지의 경로가 최대 30과 30으로 나타났다

서식

PROGRAM NAME: numtri
INPUT FORMAT:
(file numtri.in)
첫 번째 가방은 R(1<=R<=1000)을 포함하고 줄의 수를 나타낸다.
뒤에 있는 모든 행위의 숫자 피라미드의 특정 줄에 포함된 정수.
모든 공급된 정수는 마이너스이며 100보다 크지 않다.
OUTPUT FORMAT:
(file numtri.out)
얻을 수 있는 가장 큰 합을 포함하는 단독 줄.

SAMPLE INPUT

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

SAMPLE OUTPUT

30

DP 입문 문제.
상태 이동 방정식:ans[j]=max(ans[j],ans[j+1])+num[i][j];

/*
ID: your_id_here
PROG: numtri
LANG: C++
*/
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int i,j,n,num[1005][1005],* ans;

int main() {
    int i;
    freopen("numtri.in","r",stdin);
    freopen("numtri.out","w",stdout);
    while(1==scanf("%d",&n)) {
        ans=num[n-1];
        for(i=0;i<n;++i) {
            ans[i]=0;
            for(j=0;j<=i;++j)
                scanf("%d",&num[i][j]);
        }
        for(i=n-2;i>=0;--i)
            for(j=0;j<=i;++j)
                ans[j]=max(ans[j],ans[j+1])+num[i][j];
        printf("%d
",ans[0]);
    }
    return 0;
}