首页 > 代码库 > 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