最大矩阵连乘次数
Time Limit:500MS Memory Limit:65536KTotal Submit:128 Accepted:72
Description
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最大。
Input
输入包含多组测试数据。第一行为一个整数C，表示有C组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n(n≤10)，表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开.
Output
你的输出应该有C行，即每组测试数据的输出占一行，它是计算出的矩阵最大连乘积次数.
Sample Input
1 3 10 100 5 50
Sample Output
75000
Source
wangzhiqun
[Submit] [Go Back] [Status] [Discuss]
// 13241 wupanlei 1071 Accepted 868K 15MS G++ 0.66K 2009-06-25 20:13:25 #include < iostream > #define MAX 1000 using namespace std; int dp[MAX][MAX],p[MAX],n; void Init(){ int i; for (i = 0 ;i <= n;i ++ ) { scanf( " %d " , & p[i]); }} void MatrixChain(){ int i,r,j,k; for (i = 1 ;i <= n;i ++ ) dp[i][i] = 0 ; for (r = 2 ;r <= n;r ++ ) for (i = 1 ;i <= n - r + 1 ;i ++ ) { j = r + i - 1 ; dp[i][j] = dp[i][i] + dp[i + 1 ][j] + p[i - 1 ] * p[i] * p[j]; for (k = i;k < j;k ++ ) { int temp = dp[i][k] + dp[k + 1 ][j] + p[i - 1 ] * p[k] * p[j]; if (temp > dp[i][j]) dp[i][j] = temp; } } printf( " %d\n " ,dp[ 1 ][n]);} int main(){ int T; scanf( " %d " , & T); while (T -- ) { scanf( " %d " , & n); Init(); MatrixChain(); } return 0 ;}
转载于:https://www.cnblogs.com/forever4444/archive/2009/06/25/1511213.html
