完全加括號(hào)的矩陣連乘積
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:437
Accepted:143
Description
根據(jù)給定的完全加括號(hào)的矩陣,求最小的矩陣連乘積.
Input
第一行為正整數(shù)N,表示有N組測(cè)試數(shù)據(jù)
每組測(cè)試數(shù)據(jù)的第一行為n,表示有n個(gè)矩陣,2<=n<=50;
接下去的n行,每行有兩個(gè)整數(shù)x和y,表示第ni個(gè)矩陣是x*y的
Output
對(duì)行每組數(shù)據(jù),輸出一行,每行一個(gè)整數(shù),最小的矩陣連乘積.
我們保證輸出的結(jié)果在2^64之內(nèi).
Sample Input
1
4
50 10
10 40
40 30
30 5
Sample Output
10500
Source
ECNU算法作業(yè)
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