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; }
这个可以发代码的叫 👿 什么玩意?
SyntaxHighlighter 2…. 💡