misschuer

常用链接

统计

积分与排名

百事通

最新评论

矩阵连乘问题 运气

#include <iostream>
using namespace std;

int main()
{
    
int t , n , i , m , temp , j , k;
    
    
int p[ 100 ] , dp[ 100 ][ 100 ];
    
    cin 
>> t;
    
    
while (t --)
    
{
        cin 
>> n;
        
        m 
= n;
        
        n 
++;
        
        i 
= 0;
        
        
while (n --)
        
{
            scanf (
"%d" , &p[ i ]);
            
            i 
++;
        }

        
        
for (i = 1 ; i <= m ; ++ i)
            
            dp[ i ][ i ] 
= 0;
        
        
for(i = 1 ; i < m ; ++ i )
            
            dp[ i ][i 
+ 1= p[i - 1* p[ i ] * p[i + 1];
        
        
for (i = 1 ; i < m ; ++ i)
            
            
for(j = 3 ; j <= m ; ++ j)
                
                
for(k = i ; k < j ; ++ k)
                
{
                    
                    
if (k == i )
                    
{
                        dp[ i ][ j ] 
= dp[ i ][ k ] + dp[ k + 1][ j ] + p[i - 1* p[ k ] * p[ j ];;
                        
                        
continue ;
                    }


                    temp  
= dp[ i ][ k ] + dp[ k + 1][ j ] + p[i - 1* p[ k ] * p[ j ];

                    
if (dp[ i ][ j ] > temp)

                          dp[ i ][ j ] 
= temp;
                        
                }



                printf (
"%d\n" , dp[m - 2][ m ]);
                            
    }


    
return 23;
}

posted on 2009-04-20 18:54 此最相思 阅读(165) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理