算法提高 矩阵乘法

 算法提高 矩阵乘法  

时间限制：3.0s   内存限制：256.0MB

问题描述

　　有n个矩阵，大小分别为a0*a1, a1*a2, a2*a3, ..., a[n-1]*a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。
　　两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。

输入格式

　　输入的第一行包含一个整数n，表示矩阵的个数。
　　第二行包含n+1个数，表示给定的矩阵。

输出格式

　　输出一个整数，表示最少的运算次数。

样例输入

3
1 10 5 20

样例输出

150

数据规模和约定

　　1<=n<=1000, 1<=ai<=10000。

 

使用动态规划，枚举的是长度len ,这样就可以不断的加长，最后得出结果；

注意：

　　结果使用long long保存，因为容易溢出

　　

 

/*
　　long long取值范围：
　　最大 922,3372,0368,5477,5807
　　最小-922,3372,0368,5477,5808
　　长度是19位，记住大致的位数，防止书写的时候范围忘记。
*/
#include<cstdio> 
#include <iostream> 
#include <cstring> 
#include <algorithm>
 using   namespace   std;
  int   n;
  long   long  a[ 1010 ],dp[ 1010 ][ 1010  ];
  int  main( void  ){
    cin  >>  n;
    n  = n +  1  ;
      for ( int  i= 1 ;i<=n;i++ )
        cin  >>  a[i];        
      for ( int  i= 1 ;i<=n;i++ )
          for ( int  j= 1 ;j<=n;j++ )
            dp[i][j]  =  10000000000000000  ;    
    
            
      for ( int  i= 1 ;i<n;i++ )
        dp[i][i + 1 ] =  0  ;        
      for ( int  len= 3 ;len<=n;len++ ){
          for ( int  i= 1 ;i<=n-len+ 1 ;i++ ){
              int  j=i+len- 1  ;
              for ( int  k=i+ 1 ;k<j;k++ ){
                dp[i][j]  = min(dp[i][k]+dp[k][j]+a[i]*a[k]* a[j],dp[i][j]);
            } 
        }
    }
    
    cout  << dp[ 1  ][n];
      return   0  ;
} 

 

查看更多关于算法提高 矩阵乘法的详细内容...