数塔
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 51094 Accepted Submission(s): 30081
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
DP裸题，每一个节点记录走到该节点的最大和，每一个节点的最大和等于当前节点与两个父节点之中较大值的和。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <cstdio> #include <string> #define MAX (int a,int b) (a>b)?a:b; int tower[150][150]; int main() { int n; scanf("%d", &n); for (int m = 1; m <= n; m++) { int h,cache; memset(tower, sizeof(tower), 0); scanf("%d", &h); for (int i=1;i<=h;i++) for (int j=1; j <= i; j++) { scanf("%d",&cache); tower[i][j] = cache + ((tower[i - 1][j - 1] > tower[i - 1][j]) ? tower[i - 1][ j - 1] : tower[i - 1][ j]); } int max = 1; for (int i=1; i <= h; i++) if (tower[h][i] > tower[h][max]) max = i; printf("%d\n", tower[h][max]); } } |