数塔
Time Limit:2000MS
Memory Limit:30000KB
Total Submit:375
Accepted:197
Description
有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最小。
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
Input
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
Output
对于每个测试实例，输出可能得到的最小和。
并在下一行输出路径。形势参见sample。
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
这个题目的数据只是为了方便大家看，读入的时候不需考虑多余的空格和换行
Sample Output
17
Source
ECNU算法作业
自底向上动态规划：
1 #include <iostream>
2
3 using namespace std;
4
5 const int L = 103;
6
7 int f[ L ][ L ], a[ L ][ L ];
8
9 int main(){
10 int td, n, i, j;
11 cin >> td;
12 while( td-- ){
13 cin >> n;
14 for( i = 1; i <= n; ++i ){
15 for( j = 1; j <= i; ++j ){
16 cin >> a[ i ][ j ];
17 }
18 }
19 for( j = 1; j <= n; ++j ){
20 f[ n ][ j ] = a[ n ][ j ];
21 }
22 for( i = n - 1; i > 0; --i ){
23 for( j = 1; j <= i; ++j ){
24 f[ i ][ j ] = a[ i ][ j ] + ( f[ i + 1 ][ j ] > f[ i + 1 ][ j + 1] ? f[ i + 1 ][ j + 1 ] : f[ i + 1 ][ j ] );
25 }
26 }
27 cout << f[ 1 ][ 1 ] << endl;
28 }
29 return 0;
30 }
31