ZOJ 1094 Matrix Chain Multiplication

于 2011年02月3日 发布在 算法&&ACM 跳到评论

ZOJ 1094 Matrix Chain Multiplication

矩阵链乘的时候,不同的结合方式所需要的运算次数不同,肯定存在一个乘法次数最少的结合方式(可以用dp求出),此题以此为背景,给出结合方式,求出所需要的乘法次数.算是经典的栈的应用,维护两个栈,KUO是括号的栈,M表示矩阵栈,从每一个表达式的开始,遇到左括号和矩阵就压入相应的栈,遇到右括号就进行栈顶两个元素的运算,直到最后。如果某两个元素不能相乘,输出error

#include<iostream>
#include<string>
#include<cstring>
#include<stack>

using namespace std;
struct MATRIX
{
    int hang,lie;
}m[26],t,A,B;
int main(void)
{
    char c;
    int N,i,TotalCount,error;
    string ss;
    stack<char> KUO;
    stack<MATRIX> M;//两个栈

    cin >> N;
    for( i = 0; i < N; i++ )
    {
        cin >> c;
        cin >> m[c-'A'].hang >> m[c-'A'].lie;
    }
    while( cin >> ss )
    {
        TotalCount = error = 0;
        for( i = 0; i < ss.length(); i++ )
        {
            if( ss[i] == '(' )//左括号压入
                KUO.push('(');
            else if( isalpha( ss[i] ) )//矩阵压入
                M.push( m[ ss[i]-'A' ] );
            else
            {
                KUO.pop();
                B = M.top();M.pop();
                A = M.top();M.pop();
                if( A.lie != B.hang )
                    {error = 1;break;}
                TotalCount += A.hang*A.lie*B.lie;
                t.hang = A.hang;
                t.lie  = B.lie;
                M.push(t);
            }
        }
        while( !KUO.empty() ) KUO.pop();
        while( !M.empty() ) M.pop();//两个栈清空

        if( error ) cout << "error\n";
        else cout << TotalCount << endl;
    }
    return 0;
}

本文共有 2条评论 | 沙发:文章评论

  1. Scriptkids说道:

    这个可以发代码的叫 :evil: 什么玩意?

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)