题目描述

数字三角

样例

#include<bits/stdc++.h>
using namespace std;


const int N = 510;
int f[N][N],m[N][N];
int INF = 0x3f3f3f3f;
int n;

int main()
{
    cin >> n;

     for(int i = 1; i<= n; i ++ )
      for(int j = 1; j <= i; j ++ )
          cin >> m[i][j];


     for(int i = 1; i <= n; i ++ )
       for(int j = 0; j <= n; j ++ )
          f[i][j] = -INF;


      for(int i = 1; i <= n; i ++ )
       for(int j = 1; j <= i; j ++ )
             f[i][j] = max(f[i-1][j-1],f[i-1][j]) + m[i][j];

     int maxn = - 1e5;
     for(int i = 1;i <= n; i ++ )
        maxn = max(f[n][i],maxn);


      cout << maxn  << endl ;


    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla