完全加括号的矩阵连乘积
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, 0x7f, sizeof( 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