數塔問題（DP算法）自底向上計算最大值，dp算法

數塔問題（DP算法）自底向上計算最大值，dp算法

Input

輸入數據首先包括一個整數C,表示測試實例的個數，每個測試實例的第一行是一個整數N(1 <= N <= 100)，表示數塔的高度，接下來用N行數字表示數塔，其中第i行有個i個整數，且所有的整數均在區間[0,99]內。

Output

對於每個測試實例，輸出可能得到的最大和，每個實例的輸出占一行。

Sample Input

Sample Output

  1 #include<iostream>
  2 #include<math.h>
  3 #include<malloc.h>
  4 using namespace std;
  5 
  6 int num=0;
  7 
  8 typedef struct Tree
  9 {
 10    int val;
 11    int max;
 12    struct Tree*left;//左分支節點
 13    struct Tree*right;//右分支節點
 14    struct Tree*sib;//兄弟節點
 15    struct Tree*next;//linenumber
 16    struct Tree*pre;//前繼行
 17 }Tree,*TreeNode;
 18 
 19 TreeNode first;
 20 
 21 
 22 void construction(int i,int j,int loc,int col)//構造樹形結構
 23 {
 24     int linenum;
 25     linenum=j;//return the linenumber;
 26 
 27     int k;
 28     if(linenum==1)
 29         first->val=i;
 30     else{
 31     TreeNode p;
 32     p=first;
 33 
 34 /*    for(k=1;k<linenum-1;k++)//鎖定行
 35     {
 36         p=p->next;
 37     }*/
 38     while(p->next!=NULL)
 39         p=p->next;//鎖定行
 40 
 41     TreeNode q;
 42     q=(TreeNode)malloc(sizeof(Tree));
 43     q->val=i;
 44     q->left=NULL;
 45     q->right=NULL;
 46     q->next=NULL;
 47     q->sib=NULL;
 48     //賦值
 49 
 50     
 51     if(col==1)//處理第一列的情況
 52     {
 53         p->next=q;
 54         q->pre=p;
 55         q->sib=NULL;
 56         q->next=NULL;
 57     
 58 
 59     }
 60     else
 61     {
 62         if(col==2)
 63         {}
 64         else
 65         {
 66             while(p->sib!=NULL)
 67             {
 68         
 69             p=p->sib;
 70             }
 71         }
 72         
 73         p->sib=q;
 74         q->sib=NULL;
 75         
 76 
 77     }
 78 
 79 
 80 //返回上一行
 81     
 82     p=first;
 83     for(k=1;k<linenum-1;k++)//鎖定上一行
 84     {
 85         p=p->next;
 86     
 87     }
 88 //鎖定上一列的位置
 89     
 90     for(k=1;k<col-1;k++)
 91     {
 92     
 93         if(p->sib!=NULL)
 94             p=p->sib;
 95     }
 96 
 97     if(col==1)
 98     {
 99         
100         p->left=q;
101     
102     }
103     else if(col==linenum)//debug
104     {
105         p->right=q;
106         
107     }
108 
109     else
110     {
111         
112         p->right=q;
113     
114         p=p->sib;
115     
116         p->left=q;
117 
118     }
119 
120 
121  
122 
123 
124     }
125 
126 }
127 
128 
129 
130 void cal(TreeNode p)
131 {    
132     while(p->next!=NULL)
133         p=p->next; 
134 
135     p=p->pre;
136 
137     TreeNode q,f;
138     q=p;
139     while(q!=NULL)
140     {
141         f=q;
142         while(f!=NULL)
143         {
144             int m;
145             m=f->left->val+f->val;
146             int n;
147             n=f->right->val+f->val;
148             if(m>n)
149                 f->val=m;
150             else
151                 f->val=n;
152             f=f->sib;
153 
154         }
155         q=q->pre;
156     }
157 
158 }
159 
160 int main()
161 {
162     int input,m;
163     first=(TreeNode)malloc(sizeof(Tree));
164     first->next=NULL;
165     first->sib=NULL;
166     first->left=NULL;
167     first->right=NULL;
168     first->pre=NULL;
169     //Initial the first node
170     cin>>input;
171     m=input;
172     int j=1;
173     for(int i=1;i<=m;i++)
174     {
175         for(int k=1;k<=i;k++)
176         {
177             int a1;
178             cin>>a1;
179             construction(a1,i,j,k);
180             j++;
181         }
182     }
183     
184     
185     
186 
187      cal(first);
188      cout<<first->val<<endl;
189     return 0;
190 }