Matrix Chain Multiplication 矩阵链乘 UVA 442

╰半橙微兮° 2024-02-17 18:49 159阅读 0赞

解题思路：首先解决如何保存输入字母所对应的两个值，通过定义结构体数组nt[0]表示字符’A’,以此类推；然后通过通过栈来储存输入的字母，遇到”)”时出栈两个元素做运算（”(“ “)”不入栈）。

  1. #include
  2. #include
  3. #include
  4. #include
  5. using namespace std;
  6. struct note{
  7. int a,b;
  8. note (int a1=0,int b1=0):a(a1),b(b1){}
  9. }nt[30];
  10. stackst;
  11. int main(){
  12. int n;
  13. scanf(“%d”,&n);
  14. for(int i=0;i<n;i++)
  15. {
  16. getchar(); //吃掉换行，否则会错
  17. char ch;
  18. scanf(“%c”,&ch);
  19. int t=ch-‘A’;
  20. scanf(“%d%d”,&nt[t].a,&nt[t].b);
  21. }
  22. string str;
  23. while(cin>>str){
  24. int flag=1;
  25. int sum=0;
  26. for(int i=0;i<str.length();i++){
  27. if(isalpha(str[i]))st.push(nt[(str[i]-‘A’)]);
  28. else if(str[i]==’)’){
  29. note n1=st.top();st.pop();
  30. note n2=st.top();st.pop();
  31. if(n2.b==n1.a){
  32. sum+=n2.a*n2.b*n1.b;
  33. st.push(note(n2.a,n1.b));
  34. }
  35. else {
  36. flag=0;
  37. break;
  38. }
  39. }
  40. }
  41. if(flag)printf(“%d\n”,sum);
  42. else printf(“error\n”);
  43. }
  44. return 0;
  45. }

发表评论

表情：
评论列表 （有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

    相关 矩阵链乘

    题目：       输入n个矩阵的维度和一些矩阵的链乘表达式，输出乘法的次数。如果乘法无法进行，输出error。假定A是m\n矩阵，B是n\p的矩阵，那么A\B是m\p的

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 284 阅读