coreBugZJ

此 blog 已弃。

完全加括号的矩阵连乘积,矩阵链乘法——算法作业 3.1,EOJ 1051

完全加括号的矩阵连乘积

Time Limit:1000MS Memory Limit:30000KB
Total Submit:437 Accepted:143

Description

根据给定的完全加括号的矩阵,求最小的矩阵连乘积.

Input

第一行为正整数N,表示有N组测试数据
每组测试数据的第一行为n,表示有n个矩阵,2<=n<=50;
接下去的n行,每行有两个整数x和y,表示第ni个矩阵是x*y的

Output

对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积.
我们保证输出的结果在2^64之内.

Sample Input

1
4
50 10
10 40
40 30
30 5

Sample Output

10500

Source

ECNU算法作业



O(n^3) 的做法:

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define  L  60
 5 
 6 long long a[ L ], b[ L ], f[ L ][ L ];
 7 
 8 int main() {
 9     int td, n, d, i, j, k;
10     long long tmp;
11     scanf( "%d"&td );
12     while ( td-- ) {
13         scanf( "%d"&n );
14         for ( i = 0; i < n; ++i )
15             scanf( "%lld%lld"&a[ i ], &b[ i ] );
16         memset( f, 0x7fsizeof( f ) );
17         for ( i = 0; i < n; ++i )
18             f[ i ][ i ] = 0;
19         for ( d = 1; d < n; ++d )
20         for ( i = 0; i + d < n; ++i ) {
21             j = i + d;
22             for ( k = i + 1; k <= j; ++k ) {
23                 tmp = f[ i ][ k - 1 ] + f[ k ][ j ] + a[ i ] * a[ k ] * b[ j ];
24                 if ( f[ i ][ j ] > tmp )
25                     f[ i ][ j ] = tmp;
26             }
27         }
28         printf( "%lld\n", f[ 0 ][ n - 1 ] );
29     }
30     return 0;
31 }
32 


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


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