数塔

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 16   Accepted Submission(s) : 6

Problem Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的： 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 已经告诉你了，这是个DP的题目，你能AC吗?   Input 输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。   Output 对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。   Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5   Sample Output 30   Source 2006/1/15 ACM程序设计期末考试 #include<iostream> #include<string> #include<math.h> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std; int main() { int num; cin>>num; while(num--) { int a[101][101],i,j,h; cin>>h; for(i=1;i<=h;i++) for(j=1;j<=i;j++) cin>>a[i][j]; for(i=h-1;i>=0;i--) for(j=1;j<=i;j++) a[i][j]+=max(a[i+1][j],a[i+1][j+1]);//每次取最大值 cout<<a[1][1]<<endl; } return 0; }