Pku 1651 Multiplication Puzzle

#include < stdio.h >

int n;

int r[ 110 ][ 110 ];

int p[ 110 ];

int main()

{

while ( scanf( " %d " , & n) != EOF )

{

for ( int i = 0 ; i < n; ++ i )

{

scanf( " %d " , & p[i] );

r[i][i] = 0 ; r[i + 1 ][i] = 0 ; r[i][i + 1 ] = 0 ;

}

for ( int d = 2 ; d < n; ++ d )

for ( int i = 0 ; i < n - d; ++ i )

{

int j = i + d;

r[i][j] = r[i + 1 ][j] + p[i] * p[i + 1 ] * p[j];

for ( int k = i + 1 ; k < j; ++ k )

{

int t = r[i][k] + r[k][j] + p[i] * p[k] * p[j];

if ( t < r[i][j] ) r[i][j] = t;

}

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

}

return 0 ;

}

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

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: pku 1691 Painting A Board 状态压缩DP Pku 1276 Cash Machine Pku 1651 Multiplication Puzzle 矩阵连乘 Pku 1023 The Fun Number System Pku 1032 Parliament Pku 1046 Color Me Less Pku 1080 Human Gene Functions Pku 3096 Surprising Strings Pku 1745 Divisibility

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类