http://acm.hdu.edu.cn/showproblem.php?pid=2084
用一个二维数组保存当前点往上走所能有的最大和
//c++的输入流std::cin很慢，可以使用ios::sync_with_stdio(false)加速。
#include <iostream>
#include <algorithm> #include <cstring> using namespace std; int subsum[101][101]; int vex[101][101]; int main(void){
ios::sync_with_stdio(false);
int T, N; cin >> T; while (T--) { cin >> N; memset(subsum, 0, sizeof(subsum)); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= i; ++j) { cin >> vex[i][j]; subsum[i][j] += vex[i][j] + max(subsum[i - 1][j - 1], subsum[i - 1][j ]); } } int ans = 0; // for (int i = 1; i <= N; ++i) // { // for (int j = 1; j <= N; ++j) // cout << subsum[i][j] << ' '; // cout << endl; // } for (int j = 1; j <= N; ++j) if (subsum[N][j] > ans) ans = subsum[N][j]; cout << ans << endl; } }