POJ2246-Matrix Chain Multiplication

淡淡的烟草味﹌ 2021-11-26 13:18 199阅读 0赞

[http://poj.org/problem?id=2246][http_poj.org_problem_id_2246]

矩阵相乘，不明白方法的同学去看一下线性代数~~~

#include<stdio.h>
    typedef struct
    {
        int mults,rows,cols;
    }triple;
    int rows[256],cols[256],p;
    char e[100],error;               
    triple expression()
    {
        triple t,t1,t2;
        if(e[p]=='(') 
        {
            p++;
            t1=expression();
            t2=expression();
            p++;
            if(t1.cols!=t2.rows) 
               error=1;  
            t.rows=t1.rows;
            t.cols=t2.cols;
            t.mults=t1.mults+t2.mults+t1.rows*t1.cols*t2.cols;
        }
        else           
        {
            t.rows=rows[e[p]];
            t.cols=cols[e[p]];
            t.mults=0;
            p++;
        }
        return t;  
    }
    int main(void)
    {
        char c;
        int i,n,ro,co;
        triple t;
        scanf("%d%c",&n,&c);
        for(i=0;i<n;i++)
        {
            scanf("%c %d %d",&c,&ro,&co);  
            getchar();
            rows[c]=ro;
            cols[c]=co;
        }
        while(gets(e)!=NULL)              
        {
            p=error=0;          
            t=expression();      
            if(error)              
               printf("error\n");
            else
               printf("%d\n",t.mults);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/YogurtShen/archive/2012/08/28/2661006.html

[http_poj.org_problem_id_2246]: http://poj.org/problem?id=2246

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

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

相关阅读

相关 Matrix Chain Multiplication 矩阵链乘 UVA 442

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

╰半橙微兮°/ 2024年02月17日 18:49/ 0 赞/ 51 阅读

相关【POJ2248】Addition Chains

Description 给定整数n，构造一个递增的正整数序列使得a1=1,am=n,且对于任意的k（1≤k≤m）都存在ak=ai\+aj,最小化序列的长度（即最小化m）

浅浅的花香味﹌/ 2023年06月05日 08:51/ 0 赞/ 13 阅读

相关洛谷-UVA442 矩阵链乘 Matrix Chain Multiplication

题目描述 [PDF][] ![format_png][] 输入格式 ![format_png 1][] 输出格式 ![format_png 2][]

电玩女神/ 2023年05月29日 09:17/ 0 赞/ 11 阅读

相关矩阵链乘（Matrix Chain Multiplication）

题目描述假设你必须评估一种表达形如 ABCDE，其中 A,B,C,D,E是矩阵。既然矩阵乘法是关联的，那么乘法的顺序是任意的。然而，链乘的元素数量必须由你选择的赋值顺

拼搏现实的明天。/ 2022年12月01日 01:21/ 0 赞/ 123 阅读

相关【日常学习】【栈】【表达式求值】Uva442 - Matrix Chain Multiplication题解

之前一直没有写过栈的典型程序，这里写一个。这个程序完全是我独立写出来的，我还没有看ruka上的标程，或许会有些不同。题目来源：University of Ulm Local

￡神魔★判官ぃ/ 2022年08月07日 02:00/ 0 赞/ 14 阅读

相关 poj-1426 Find The Multiple

Find The Multiple <table style="margin-left:0px;"> <tbody> <tr> <td><strong>Ti

绝地灬酷狼/ 2022年06月01日 01:17/ 0 赞/ 157 阅读

相关 poj 3233 Matrix Power Series

题目链接：[点我][Link 1] Description Given a n × n matrix A and a positive integer k, find t

爱被打了一巴掌/ 2022年05月15日 00:09/ 0 赞/ 145 阅读

相关 POJ2246-Matrix Chain Multiplication

[http://poj.org/problem?id=2246][http_poj.org_problem_id_2246] 矩阵相乘，不明白方法的同学去看一下线性代数~~~

淡淡的烟草味﹌/ 2021年11月26日 13:18/ 0 赞/ 200 阅读

相关 POJ 1465【Multiple】

描述 a program that, given a natural number N between 0 and 4999 (inclusively), and M d

悠悠/ 2021年11月10日 08:26/ 0 赞/ 217 阅读

相关 POJ 1426 Find The Multiple

Find The Multiple <table> <tbody> <tr> <td><span style="font-size:16px;"><stro

女爷i/ 2021年09月30日 23:46/ 0 赞/ 214 阅读