POJ2246-Matrix Chain Multiplication

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

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;
}