coreBugZJ

此 blog 已弃。

数塔——算法作业 3.4,EOJ 1111

数塔

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 


posted on 2011-04-18 16:15 coreBugZJ 阅读(150) 评论(0)  编辑 收藏 引用 所属分类: 课内作业


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理