| 123456789101112131415161718192021 |
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int N = 100;
- int dp[N], tri[N][N];
- // dp[i] means the max sum from the ith col of curr row to the last row.
- int main() {
- int n;
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- for (int j = 0; j < i + 1; j++) scanf("%d", &tri[i][j]);
- memcpy(dp, tri[n - 1], n * sizeof(int));
- for (int i = n - 1; 0 < i; i--)
- for (int j = 0; j < i; j++) dp[j] = tri[i - 1][j] + max(dp[j], dp[j + 1]);
- printf("%d\n", dp[0]);
- }
|
