蓝桥杯2020年第十一届省赛真题-数字三角形

   *              *                *
  /              /                  \ 
 *   *          *   *            *   *
  \              \                  / 
*  *  *        *  *  *          *  *  *
                 /                  \
             *  *  *  *        *  *  *  *  
             
             
             
            //经观察得n为偶数时，最后一层落在的点一定在n/2或n/2+1,而n为奇数时，最后一层落在的点一定在n/2+1
f[i][j]表示所有从头开始往下走到第i层第j个的路径的最大值

#include <bits/stdc++.h>


using namespace std;
const int N=110;

int n;
int g[N][N];
int f[N][N];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=i;j++)
      {
          cin>>g[i][j];
      }
  }
  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])+g[i][j];
      }
  }
  if(n%2==0)cout<<max(f[n][n/2],f[n][n/2+1]);
  else cout<<f[n][n/2+1];
  return 0;
}