时间限制: 1 s

 空间限制: 16000 KB

 题目等级 : 黄金 Gold

题目描述 Description

从数字三角形的顶部（如图，第一行的5表示行数）到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，且！！！！！！！！！

==================================================================================

==================================================================================

你有一次机会可以把任何一个数重复加一遍。

==================================================================================

==================================================================================

和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

==================================================================================

==================================================================================

题目看仔细！！若AC欢迎公开题解（不知道怎么加的看右上角）！！

==================================================================================

==================================================================================

如果空间复杂度不够去4832，同一道题但空间复杂度要求不高（但是4832白银）

输入描述 Input Description

第一行：一个数，表示行数。

接下来n行为数塔

输出描述 Output Description

一个数即最优结果

样例输入 Sample Input

5

1

1 3

1 1 3

1 1 1 3

7 1 1 1 3

样例输出 Sample Output

18

数据范围及提示 Data Size & Hint

三角形行数不大于1000。最大和不大于maxlongint

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=1e3+;

int n,a[N][N],f[N][];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        for(int j=;j<=i;j++){

            scanf("%d",&a[i][j]);

        }

    }

    for(int i=n;i;i--){

        for(int j=;j<=i;j++){

            f[j][]=max(max(f[j][],f[j+][])+*a[i][j],max(f[j][],f[j+][])+a[i][j]);

            f[j][]=max(f[j][],f[j+][])+a[i][j];

        }

    }

    printf("%d",max(f[][],f[][]));

    return ;

}