#include  < stdio.h >

struct   Matrix
{
    
int  r,c;
}
;

int      n;
int      r[ 110 ][ 110 ];
Matrix  p[
110 ];    //    The Matrix with row and column

/*

6
30 35 35 15 15 5 5 10 10 20 20 25

*/


int  main()
{
    
while ( scanf( " %d " , & n) !=  EOF )
    
{
        
for int  i =   0 ; i <  n;  ++ i )
        
{
            scanf(
" %d%d " & p[i].r,  & p[i].c );
            r[i][i]
=   0 ;
        }

        
        
for int  d =   1 ; d <  n;  ++ d )
            
for int  i =   0 ; i <  n -  d;  ++ i )
            
{
                
int  j =  i +  d;
                
                r[i][j]
=  r[i + 1 ][j] +  p[i].r *  p[i].c *  p[j].c;
                
                
for int  k =  i + 1 ; k <  j;  ++ k )
                
{
                    
int  t =  r[i][k] +  r[k + 1 ][j] +  p[i].r *  p[k].c *  p[j].c;
                    
                    
if ( t <  r[i][j] ) r[i][j] =  t;
                }

            }

    
        printf(
" %d\n " , r[ 0 ][n - 1 ] );
    }

    
    
return   0 ;
}

posted on 2008-11-03 17:05 Darren 阅读(520) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

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