题目：The Triangle (POJ 1163)

链接：

#include 
      

#include 
      

using namespace std;

int main(int argc, char **argv)

{

int data[101][101];

int sum[101][101];

int n;

memset(data, 0, sizeof(data));

memset(sum, 0, sizeof(sum));

cin >> n;

for (int i = 1; i <= n; ++i)

{

for (int j = 1; j <= i; ++j)

{

cin >> data[i][j];

}

}

sum[1][1] = data[1][1];

for (int i = 2; i <= n; ++i)

{

for (int j = 1; j <= i; ++j)

{

if (j >=1 && j <= i - 1 && data[i][j] + sum[i - 1][j] > sum[i][j])

{

sum[i][j] = data[i][j] + sum[i - 1][j];

}

if (j - 1 >= 1 && j - 1 <= i - 1 && data[i][j] + sum[i - 1][j - 1] > sum[i][j])

{

sum[i][j] = data[i][j] + sum[i - 1][j - 1];

}

}

}

int max = 0;

for (int j = 1; j <= n; ++j)

{

if (sum[n][j] > max)

{

max = sum[n][j];

}

}

cout << max;

return 0;

}