#include <stdio.h> #include <iostream> #include <string.h> #include <string> #include <algorithm> using namespace std; int main() { int t; cin >> t; while (t--) { int a[100][100], f[100][100]; int n; scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) cin >> a[i][j]; 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], f[i - 1][j]) + a[i][j]; int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, f[n][i]); cout << ans; return 0; } } |
Double click to view unformatted code.