ACM. Hj70 matrix multiplication calculation amount estimation ●●

HJ70 Matrix multiplication calculation amount estimation ●●

describe

The computation of matrix multiplication is strongly related to the order of matrix multiplication .
for example ：
A It's a 50×10 Matrix ,B yes 10×20 Matrix ,C yes 20×5 Matrix
Calculation ABC There are two orders ：((AB)C) perhaps (A(BC)), The former needs to calculate 15000 Times multiplication , The latter only needs 3500 Time .
Write a program to calculate the multiplication times required for different calculation sequences .

Data range ： The number of matrices ：$1\le n\le 15$, Number of rows and columns ：$1\le ro{w}_i,co{l}_i\le 100$, Ensure that the calculation order of the given string representation is unique .
Advanced ： Time complexity ：$O(n)$, Spatial complexity ：$O(n)$

Input description ：

Input multiple lines , First enter the number of matrices to calculate the multiplication n, The number of rows per matrix , Number of columns , in total 2n Number of numbers , Finally, enter the rule to calculate ;
The calculation rule is a string , It consists only of left and right parentheses and capital letters （‘A’~‘Z’） form , Make sure the parentheses match and the input is legal ！

Output description ：

Output the number of multiplications to be performed

Example

Input ：
3
50 10
10 20
20 5
(A(BC))
Output ：
3500

Answer key

1. Stack

First of all, we should know the process and law of matrix operation ,

With $[m,n]$ Express $m$ That's ok $n$ Columns of the matrix , With $[m,n]\ast [n,p]$ As an example, the matrix multiplication rules are explained ：

• The first matrix takes a row , The second matrix takes a column , The calculation is corresponding multiplication , Yes $n$ Times multiplication .
• It's the row where the first matrix just participated in the operation , All the columns of the second matrix （ common p Column ）, There will be $n\ast p$ Times multiplication
• All rows of the first matrix （ common $m$ That's ok ） Participate in operation , Co existing $n\ast p\ast m$ Secondary multiplication .
• obtain $[m,n]\ast [n,p]$ Co existing $n\ast p\ast m$ Secondary multiplication , The matrix obtained after the operation is $[m,p]$

therefore , We can use stack to judge and calculate , Traversal string ,

• When the character is an open parenthesis , skip ;
• When the character is a letter , Convert to the corresponding matrix size and add it to the stack ;
• When the character is a closing bracket , Take out the two matrices at the top of the stack for operation , And the size of the matrix obtained after the operation is pushed onto the stack .

The length of the string is n + 2 * ( n - 1),n Is the number of matrices .

• Time complexity ：O(N), The cost of traversing all matrices or strings that specify the order of computation , among N Is the number of matrices
• Spatial complexity ：O(N), The size of the space in which the matrix data is stored , And some other equal cost space applications

#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;

int main(){
    
    int n;
    while(cin >> n){
    
        vector<vector<int>> m(n, vector<int>(2, 0));  // m[i][0]  Said line 
        for(int i = 0; i < n; ++i){
    
            cin >> m[i][0] >> m[i][1];
        }
        stack<vector<int>> st;
        int ans = 0;
        for(int i = 0; i < 3*n-2; ++i){
    		//  The length of the string is  n + 2*(n-1)
            char ch;
            cin >> ch;
            if(ch == '('){
    					//  The left parenthesis does not handle 
                continue;
            }else if(ch == ')'){
    			//  Right bracket , Operate on the first two matrices 
                vector<int> a(2, 0);
                vector<int> b(2, 0);
                b = st.top();				// a * b
                st.pop();
                a = st.top();
                st.pop();
                ans += a[0] * a[1] * b[1];	//  The number of calculations is  a That's ok  * a Column  * b Column 
                st.emplace(vector<int>{
    a[0], b[1]});	//  Push the calculated new matrix size onto the stack 
            }else{
    
                st.emplace(m[ch-'A']);		//  Letter , Stack the corresponding matrix size 
            }
        }
        cout << ans << endl;
    }
    return 0;
}