hoj 1071 最大矩阵连乘次数

最大矩阵连乘次数

Time Limit:500MS  Memory Limit:65536K
Total 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;
}