superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1094 - Matrix Chain Multiplication

Posted on 2008-03-23 22:12 superman 阅读(705) 评论(0)  编辑 收藏 引用 所属分类: ZOJ
 1 /* Accepted 1094 C++ 00:00.00 844K */
 2 #include <map>
 3 #include <stack>
 4 #include <string>
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 struct Matrix { int r, c; };
10 
11 int main()
12 {
13     int n;
14     char name;
15     map<char, Matrix> matrix;
16     
17     cin >> n;
18     for(int i = 0; i < n; i++)
19     {
20         cin >> name;
21         cin >> matrix[name].r >> matrix[name].c;
22     }
23     
24     string exp;
25     while(cin >> exp)
26     {
27         if(exp.size() == 1)
28         {
29             cout << 0 << endl;
30             continue;
31         }
32         
33         int i, count = 0;
34         stack<Matrix> mst;
35         for(i = 0; i < exp.size(); i++)
36         {
37             if(exp[i] == '(')
38                 continue;
39             if(exp[i] == ')')
40             {
41                 Matrix b = mst.top(); mst.pop();
42                 Matrix a = mst.top(); mst.pop();
43                 if(a.c != b.r)
44                 {
45                     cout << "error" << endl;
46                     break;
47                 }
48                 count += a.r * b.r * b.c;
49                 Matrix tmp = {a.r, b.c};
50                 mst.push(tmp);
51             }
52             else
53                 mst.push(matrix[exp[i]]);
54         }
55         if(i == exp.size())
56             cout << count << endl;
57     }
58     
59     return 0;
60 }
61 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理