首页 > 代码库 > UVa 348 - Optimal Array Multiplication Sequence
UVa 348 - Optimal Array Multiplication Sequence
题目:矩阵连乘,求最小运算次数,输出运算优先级(用括号给出)。
分析:dp,区间动态规划。
状态:设DP[ l ][ s ]为以 s 开始长度为 l 的区间的 矩阵乘积的最小值;
阶段:区间长度;
决策:DP[ l ][ s ] = min(DP[ k ][ s ] + DP[ l-k ][ s+k ] + 乘法代价){ 1<k<l };
记录每一步运算的位置,递归输出计算方式即可。
说明:zoj1276(2011-09-19 01:38)。
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; struct node { int R,C; }X[ 11 ]; int DP[ 11 ][ 12 ]; int DI[ 11 ][ 12 ]; void print( int l, int s ) { if ( l > 1 ) { cout << "("; print( DI[ l ][ s ], s ); cout << " x "; print( l-DI[ l ][ s ], s+DI[ l ][ s ] ); cout << ")"; }else cout << "A" << s; } int main() { int n,t = 1; while ( cin >> n && n ) { for ( int i = 1 ; i <= n ; ++ i ) cin >> X[ i ].R >> X[ i ].C; memset( DP, 0, sizeof( DP ) ); for ( int l = 2 ; l <= n ; ++ l ) for ( int s = 1 ; s+l-1 <= n ; ++ s ) { DP[ l ][ s ] = 0xffffff; for ( int k = 1 ; k < l ; ++ k ) { int Temp = DP[ k ][ s ] + DP[ l-k ][ s+k ] + X[ s ].R*X[ s+k ].R*X[ s+l-1 ].C; if ( DP[ l ][ s ] > Temp ) { DP[ l ][ s ] = Temp; DI[ l ][ s ] = k; } } } //cout << DP[ n ][ 1 ] << endl; cout << "Case " << t ++ << ": "; print( n, 1 ); cout << endl; } }
UVa 348 - Optimal Array Multiplication Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。