acwing 898 数字三角形

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 510 , INF = 1e9 + 10 ;
int a[N][N] , f[N][N];
int n ;
 
int main(){
  cin >> n ;
  for(int i = 1 ; i <= n ; i ++){
    for(int j = 1; j <= i ; j ++){
      cin >> a[i][j] ;
    }
  } 
//  for(int i = 0 ; i <= n ; i ++){
//      for(int j = 0 ; j <= i + 1; j ++ ) // memset只能将int 二进制后八位 ；
//          f[i][j] = -1e9 ;               //对于数组b的初始化
//  }
  memset(f,-INF,sizeof(f)) ;
//  for(int i = 0 ; i <+ n ; i ++){
//    for(int j = 0 ; j <= i ; j++) cout << f[i][j] << " " ;
//    cout << endl ;
//  }
  f[1][1] = a[1][1] ;
  for(int i = 2; i <= n ; i ++){
    for(int j = 1; j <= i ; j ++)\\搜索上一层的两个数
      f[i][j] = max(f[i-1][j-1] + a[i][j] , f[i-1][j] + a[i][j]) ;
    }
  }
  int ans = -INF ;
  for(int i = 1 ; i <= n; i ++) ans = max(ans , f[n][i]) ;
  cout << ans << endl ;
  return 0 ; 
}