Input
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
#include<iostream>
#include<math.h>
#include<malloc.h>
using namespace std; int num=; typedef struct Tree
{
int val;
int max;
struct Tree*left;//左分支节点
struct Tree*right;//右分支节点
struct Tree*sib;//兄弟节点
struct Tree*next;//linenumber
struct Tree*pre;//前继行
}Tree,*TreeNode; TreeNode first; void construction(int i,int j,int loc,int col)//构造树形结构
{
int linenum;
linenum=j;//return the linenumber; int k;
if(linenum==)
first->val=i;
else{
TreeNode p;
p=first; /* for(k=1;k<linenum-1;k++)//锁定行
{
p=p->next;
}*/
while(p->next!=NULL)
p=p->next;//锁定行 TreeNode q;
q=(TreeNode)malloc(sizeof(Tree));
q->val=i;
q->left=NULL;
q->right=NULL;
q->next=NULL;
q->sib=NULL;
//赋值 if(col==)//处理第一列的情况
{
p->next=q;
q->pre=p;
q->sib=NULL;
q->next=NULL; }
else
{
if(col==)
{}
else
{
while(p->sib!=NULL)
{ p=p->sib;
}
} p->sib=q;
q->sib=NULL; } //返回上一行 p=first;
for(k=;k<linenum-;k++)//锁定上一行
{
p=p->next; }
//锁定上一列的位置 for(k=;k<col-;k++)
{ if(p->sib!=NULL)
p=p->sib;
} if(col==)
{ p->left=q; }
else if(col==linenum)//debug
{
p->right=q; } else
{ p->right=q; p=p->sib; p->left=q; } } } void cal(TreeNode p)
{
while(p->next!=NULL)
p=p->next; p=p->pre; TreeNode q,f;
q=p;
while(q!=NULL)
{
f=q;
while(f!=NULL)
{
int m;
m=f->left->val+f->val;
int n;
n=f->right->val+f->val;
if(m>n)
f->val=m;
else
f->val=n;
f=f->sib; }
q=q->pre;
} } int main()
{
int input,m;
first=(TreeNode)malloc(sizeof(Tree));
first->next=NULL;
first->sib=NULL;
first->left=NULL;
first->right=NULL;
first->pre=NULL;
//Initial the first node
cin>>input;
m=input;
int j=;
for(int i=;i<=m;i++)
{
for(int k=;k<=i;k++)
{
int a1;
cin>>a1;
construction(a1,i,j,k);
j++;
}
} cal(first);
cout<<first->val<<endl;
return ;
}
