UVA 442 - Matrix Chain Multiplication 数据结构课题

2012-08-01

UVA 442 - Matrix Chain Multiplication 数据结构专题442 - Matrix Chain Multiplication513459.82%255992

UVA 442 - Matrix Chain Multiplication 数据结构专题

442 - Matrix Chain Multiplication513459.82%255992.93%

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=383

样例输入：

9A 50 10B 10 20C 20 5D 30 35E 35 15F 15 5G 5 10H 10 20I 20 25ABC(AA)(AB)(AC)(A(BC))((AB)C)(((((DE)F)G)H)I)(D(E(F(G(HI)))))((D(EF))((GH)I))

样例输出：

000error10000error350015000405004750015125

题目大意：

给出一系列的矩阵，给他们取名A ，B…… 以及它们的行数和列数。给完后，给出一系列的表达式，然后要求求出按这些表达式进行计算，会有多少次乘法步骤。

解体思路：

这题和括号匹配那题很像。关键的步骤是计算矩阵乘法次数的这个过程。

#include<cstdio>#include<cctype>#include<cstring>#include<cstdlib>#include<stack>using namespace std;int sum,n;int mat[30][2];int arr[30],prev[30], next[30];char str[1000];void solve(){    // 如过只有一个矩阵，那么直接输出结果0    if(strlen(str)==1 && isupper(str[0])){        printf("0\n");    }    else{        char copyMat[30][2];        int i,j;        // 复制一个数组进行操作。 因为后面的操作需要对这些矩阵进行修改        for(i=0; i<n; ++i){            copyMat[i][0] = mat[i][0];            copyMat[i][1] = mat[i][1];        }        sum=0;        stack<char>st;                 for(i=0; i<strlen(str); ++i){            if(str[i]=='(' || isupper(str[i]))                st.push(str[i]);            else if(str[i]==')'){                stack<char>temp;      // 当碰到‘）’时，把栈中的矩阵全都取出来进行计算                   while(isupper(st.top())){                    temp.push(st.top());                                st.pop();                }                // 把'('也弹出                st.pop();                char ex;                // 取出第一个矩阵（在原表达式中是最左边的一个）                if(!temp.empty()){                    ex=temp.top();                    temp.pop();                }                while(!temp.empty()){                    char multi = temp.top();                    temp.pop();                    // 如果左边矩阵的列数和右边矩阵的函数不同，则直接输出 error                    if(copyMat[ex-'A'][1] != copyMat[multi-'A'][0]){                        printf("error\n");                        return ;                    }                    // 计算相乘次数，加上                    sum += copyMat[ex-'A'][0]*copyMat[multi-'A'][0]*copyMat[multi-'A'][1];                    // 相乘后得到一个新矩阵，更新尺寸                    copyMat[ex-'A'][1] = copyMat[multi-'A'][1];                }                st.push(ex);            }        }          printf("%d\n",sum);    }}int main(){    freopen("input.txt", "r",stdin);    char ch;    int  i, j;    scanf("%d%*c", &n);    for(i=0; i<n; ++i){        scanf("%c %d %d%*c",&ch,&mat[i][0],&mat[i][1]);    }        while(gets(str)){        solve();    }    return 0;}

热点排行

网络基础

UVA 442 - Matrix Chain Multiplication 数据结构课题