Number Triangles

Problem Statement

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大权值。

input

第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

Output

单独的一行,包含那个可能得到的最大的和。

Sample Input

Sample Output

1

30

Constraints

对于 $100%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。

Problem Source:

USACO Training Section 1.5

IOI1994 Day1T1

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 0;
int t;    
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    int t[n+1][n+1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin >> t[i][j];
        }
    }
    int dp[n+1][n+1];//表示到达该点能达到的最大和
    memset(dp,0,sizeof(dp));
    dp[1][1] = t[1][1];
    if(n==1)//注意处理边界情况
    {
        cout << t[1][1];
        return 0;
    }
    dp[2][1] = t[2][1]+t[1][1];
    dp[2][2] = t[2][2]+t[1][1];
    if(n<3)//注意处理边界情况
    {
        cout << max(dp[2][1],dp[2][2]);
        return 0;
    }
    for(int i=3;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j] = max(dp[i-1][j-1]+t[i][j],dp[i-1][j]+t[i][j]);//状态转移 此点由上一层能到达该点的值加上此点的和的最大值确定
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    ans = max(ans,dp[n][i]);//在最后一层查找最大值
    cout << ans;
    return 0;
}