摘要
Title: HJ70 矩阵乘法计算量估算
Tag: 栈、括号
Memory Limit: 64 MB
Time Limit: 1000 ms

HJ70 矩阵乘法计算量估算

题意

矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算ABC有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数。
思路

遇到括号问题，先想到用栈解决
- 当遇到左括号，不用管
- 当遇到右括号，根据题意，将数值弹出
- 当遇到数值，压入栈即可

代码

#include <bits/stdc++.h>
#include <stack>
#include <unordered_map>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int dp[N];

signed main()
{
    // freopen("Tests/input_1.txt", "r", stdin);
    IOS;

    int n;
    cin >> n;

    unordered_map<char, PII> mp;

    char A = 'A';
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        cin >> x >> y;
        mp[A] = {x, y};
        A = A + 1;
    }

    int ans = 0;
    string s;
    cin >> s;
    stack<PII> st;

    for (auto i : s)
    {
        if (i == '(')
            continue;
        else if (i == ')')
        {

            auto a = st.top();
            st.pop();
            auto b = st.top();
            st.pop();

            ans += a.first * a.second * b.first;
            st.push({b.first, a.second});
        }
        else
        {
            st.push({mp[i].first, mp[i].second});
        }
    }

    cout << ans;

    return 0;
}

HJ70 矩阵乘法计算量估算

题意

思路

代码