三角形最大和问题

Time Limit:1000MS Memory Limit:65536K
Total Submit:79 Accepted:22

Description

现在经常有一些数学问题困扰着小明。有如下一个三角形，

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

小明想求出从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。现在想请你编一个程序实现这个问题。
说明：
（1）每一步可沿左斜线向下或右斜线向下；
（2）1＜三角形行数≤100;
（3）三角形中的数字为0,1,...,99。

Input

输入有多个实例。每个测试用例的第一行是三角形的行数n，接下来是n行数字，每行数字的个数由1开始，依次加1。

Output

输出每个测试用例的最大和（整数），每行1个。

Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

Source

DP.从下往上做递归.每一步的路程数等于与它下相邻中的最大者和本身之和.
我觉得应该是这样.
30
23 21
20 13 10
7 12 10 10
4 5 2 6 5

我想的是 把所有的路线最后的数都存起来 最后在选出最大的

我按要求大致编了一下，编译时系统没有报错，但是运算时却报错。麻烦给看看是什么问题。
我觉得问题应该主要出在给结构体数组分配内存空间和往子函数上传递结构体数组的值这两处问题上。
请各位看看如何修改。算法应该是没问题的。

#include <stdio.h>
#include <stdlib.h>

struct triangle
{
int element;
int sum;
}**p;

int Count( struct triangle ** , int );

void main()
{
int i, j;
int n;
int result;

printf( "Please input the degree of triangle:" );
scanf( "%d", &n );
p = (struct triangle **)malloc( n * n * sizeof(struct triangle) );
printf( "Please input the elements of triangle:\n" );
for( i = 0; i < n; i ++ )
{
for( j = 0; j <= i ; j ++ )
{
scanf( "%d", &p[i][j].element );
p[i][j].sum = p[i][j].element;
}
}

result = Count( p,n );
free(p);

printf( "The maximum is %d\n", result );
}

int Count( struct triangle **p , int n )
{
int i, j, temp;
int result = 0;

for( i = 0; i < n - 1; i ++ )
{
for( j = 0; j <= i; j ++ )
{
temp = p[i][j].sum + p[i + 1][j].element;
if( temp > p[i + 1][j].sum )
p[i + 1][j].sum = temp;
temp = p[i][j].sum + p[i + 1][j + 1].element;
if( temp > p[i + 1][j + 1].sum )
p[i + 1][j + 1].sum = temp;
}
}

for( j = 0; j < n; j ++ )
{
if( p[n - 1][j].sum > result )
result = p[n - 1][j].sum;
}

return result;
}

哈哈哈哈哈
自己想了很多复杂的办法 程序做出来了 但是结果总是不对 改了整整2天都没改对
结果又想了一个很简单的办法 解决了 真是哭笑不得

[此贴子已经被作者于2007-6-14 11:35:41编辑过]

别光说啊 那就把你的程序发过来学习学习啊。

我日 原来我把题理解错了。。。。。。。。。 我一直按早我的理解做的
我日啊
#include<stdio.h>
main()
{
int A[100]={0},n,l=0,o=0,d;
scanf("%d",&n);
fflush(stdin);
if(n<=0)exit(0);
scanf("%d",&d);
A[l]=d;
for(int i=1;i<n;i++)
{ scanf("%d",&d);
for(int j=0;j<i;j++,l++)
{
A[++o]=A[l]+d;
scanf("%d",&d);
A[++o]=A[l]+d;
}
fflush(stdin);
}
n=0;
for(int i=0;i<o+1;i++)
if(A[i]>n)
n=A[i];
printf("%d",n);
}

你这样似乎不行如果是
20
5 1
6 1 1
7 1 1 99
那就不行了吧？
不知道 我理解的你的意思对不对 ？

经过我的不懈努力，放弃了上边用二维数组实现的想法，终于用一维数组搞定实现了。
下边是源代码，实验过好几遍了，结果都没错。

#include <stdio.h>
#include <stdlib.h>

struct triangle
{
int element;
int sum;
}*array;

int Count( struct triangle *arr, int m, int s )
{
int i, j, temp;
int result = 0;
int n = 0;

for( i = 0; i <= (m - 1) * (m - 2) / 2; i = i + n )
{
for( j = 0; j <= n; j ++ )
{
temp = arr[i + j].sum + arr[i + j + n + 1].element;
if( temp > arr[i + j + n + 1].sum )
arr[i + j + n + 1].sum = temp;

temp = arr[i + j].sum + arr[i + j + n + 1 + 1].element;
if( temp > arr[i + j + n + 1 + 1].sum )
arr[i + j + n + 1 + 1].sum = temp;
}
n++;
}

for( i = m * (m - 1) / 2; i < s; i ++ )
{
if( arr[i].sum > result )
result = arr[i].sum;
}

return result;
}

void main()
{
int i;
int degree, size;
int result;

printf( "Please input the degree of triangle:" );
while(1)
{
scanf( "%d", &degree );
if( degree > 1 && degree <= 100 )
break;
printf( "Error input!Please try again.\n" );
printf( "Please input the degree of triangle:" );
}

size = degree * (1 + degree ) / 2;
array = (struct triangle *)malloc( size * sizeof(struct triangle) );

printf( "Please input the elements of triangle:\n" );
for( i = 0; i < size; i ++ )
{
scanf( "%d", &array[i].element );
array[i].sum = array[i].element;
}

result = Count( array , degree , size );

free(array);
printf( "The maximum is %d\n", result );
}

[此贴子已经被作者于2007-6-14 20:03:03编辑过]

早知道 就用递归了 谢谢版主指点啊
#include<stdio.h>
int s[100][100]={0};
int fun(int x,int y,int a,int b)
{
if(s[x][y]==-1)
{
b=a>b?a:b;
return b;
}
a=s[x][y]+a;
b=fun(x+1,y,a,b);
b=fun(x+1,y+1,a,b);
b=a>b?a:b;
return b;
}
main()
{
int n,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<i+1;j++)
{
scanf("%d",&s[i][j]);
}
fflush(stdin);
s[i][j]=-1;
}
for(int x=0;x<j+1;x++)
s[i][x]=-1;
printf("%d",fun(0,0,0,0));
}