【数字三角形】

题目

代码

#include <bits/stdc++.h>
using namespace std;const int N = 510;
int f[N][N];
int a[N][N];
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){cin >> a[i][j];if(i == 1 && j == 1) f[i][j] = a[i][j];else f[i][j] = INT_MIN;if(j-1 >= 1) f[i][j] = max(f[i][j], f[i-1][j-1] + a[i][j]);if(j <= i-1) f[i][j] = max(f[i][j], f[i-1][j] + a[i][j]);}}int res = INT_MIN;for(int i = 1; i <= n; i++){res = max(res, f[n][i]);}cout << res;return 0;
}