數(shù)塔
Time Limit:2000MS
Memory Limit:30000KB
Total Submit:375
Accepted:197
Description
有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最小。
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
Input
輸入數(shù)據(jù)首先包括一個整數(shù)C,表示測試實(shí)例的個數(shù)，每個測試實(shí)例的第一行是一個整數(shù)N(1 <= N <= 100)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個i個整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。
Output
對于每個測試實(shí)例，輸出可能得到的最小和。
并在下一行輸出路徑。形勢參見sample。
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
這個題目的數(shù)據(jù)只是為了方便大家看，讀入的時候不需考慮多余的空格和換行
Sample Output
17
Source
ECNU算法作業(yè)
自底向上動態(tài)規(guī)劃：
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