POJ3176

#include <STDIO.H>
#include <MALLOC.H>
#define max(a, b) (((a) > (b)) ? (a) : (b))
void GetMaxCost(int **data, int **result, int n)
{
int i, j;
for(j = 1; j <= n; j++)
{
result[n][j] = data[n][j];
}

for(i = n-1; i >= 1; i--)
{
for(j = 1; j <= i; j++)
{
result[i][j] = max(result[i + 1][j] + data[i][j], result[i + 1][j + 1] + data[i][j]);
}
}
}
void main()
{
int **data = NULL;
int **result = NULL;
int n, i, j, max;
scanf("%d", &n);
data = (int **)malloc(sizeof(int *) * (n + 1));
result = (int **)malloc(sizeof(int *) * (n + 1));
for(i = 1; i <= n; i++)
{
data[i] = malloc(sizeof(int) * (i + 1));
result[i] = malloc(sizeof(int) * (i + 1));
memset(data[i], 0, sizeof(int) * (i + 1));
memset(result[i], 0, sizeof(int) * (i + 1));
}

for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
scanf("%d", &data[i][j]);
}
}

GetMaxCost(data, result, n);

max = 0;
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
if(result[i][j] > max)
max = result[i][j];
}
}

printf("%d", max);

}

POJ3176,布布扣,bubuko.com

POJ3176

原文：http://www.cnblogs.com/jsy306/p/3729626.html