Problem1701--数字三角形

1701: 数字三角形

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 388  Solved: 170
[Submit] [Status] [Web Board] [Creator:]

Description

数字三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？（下图为n=6时的情况)







2








96
30






83
52
60




21
65
44
61


8
79
50
41
21
61
41
50
38
79
10


Input

第1行：整数n(1<=n<=1000)
第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。

Output

一行：一个整数，表示所经过数字的最大和。

Sample Input

6					
2					
96	30				
83	52	60			
21	65	44	61		
8	79	50	41	21	
61	41	50	38	79	10

Sample Output

375

HINT

#include<bits/stdc++.h>
usingnamespacestd;
intmain()
{
    inta[1005][1005];
    intn,i,j;
    cin>>n;
    for(i=2;i<=n;i++){
        for(j=1;j<=i-1;j++){
            cin>>a[i][j];
        }
    }
    for(i=2;i<=n;i++){
        for(j=1;j<=i-1;j++){
            if(a[i+1][j]>a[i+1][j+1]){
                a[i][j]=a[i][j]+a[i+1][j];
            }
            else{
                a[i][j]=a[i][j]+a[i+1][j+1];
            }
        }
    }
    cout<<a[2][1];
}

Source/Category

动态规划 

[Submit] [Status]