UVA 442 - 매트릭스 체인 곱셈 데이터 구조 주제

442-Matrix Chain Multiplication
5134
59.82%
2559
92.93%
제목 링크:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=383
제목 유형: 데이터 구조, 링크
샘플 입력:

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

샘플 출력:

0
0
0
error
10000
error
3500
15000
40500
47500
15125

제목 의 대의:
일련의 행렬 을 제시 하여 그들 에 게 A, B... 그리고 그들의 줄 수 와 열 수 를 지어 주 었 다.주어진 후에 일련의 표현 식 을 제시 한 다음 에 이 표현 식 에 따라 계산 하면 몇 번 의 곱셈 절차 가 있 는 지 구 해 야 합 니 다.
사고방식 해체:
이 문 제 는 괄호 와 일치 하 는데 그 문 제 는 매우 비슷 하 다.관건 적 인 절 차 는 행렬 곱셈 횟수 를 계산 하 는 이 과정 이다.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<stack>
using namespace std;

int sum,n;
int mat[30][2];
int arr[30],prev[30], next[30];
char str[1000];

void solve(){
    //         ，        0
    if(strlen(str)==1 && isupper(str[0])){
        printf("0
");
    }
    else{
        char copyMat[30][2];
        int i,j;
        //           。                   
        for(i=0; i<n; ++i){
            copyMat[i][0] = mat[i][0];
            copyMat[i][1] = mat[i][1];
        }
        sum=0;
        stack<char>st; 
        
        for(i=0; i<strlen(str); ++i){
            if(str[i]=='(' || isupper(str[i]))
                st.push(str[i]);
            else if(str[i]==')'){
                stack<char>temp;      
		//    ‘）’ ，                  
                while(isupper(st.top())){
                    temp.push(st.top());            
                    st.pop();
                }
                //  '('   
                st.pop();
                char ex;
                //        （             ）
                if(!temp.empty()){
                    ex=temp.top();
                    temp.pop();
                }
                while(!temp.empty()){
                    char multi = temp.top();
                    temp.pop();
                    //                    ，      error
                    if(copyMat[ex-'A'][1] != copyMat[multi-'A'][0]){
                        printf("error
");
                        return ;
                    }
                    //       ，  
                    sum += copyMat[ex-'A'][0]*copyMat[multi-'A'][0]*copyMat[multi-'A'][1];
                    //           ，    
                    copyMat[ex-'A'][1] = copyMat[multi-'A'][1];
                }
                st.push(ex);
            }
        }  
        printf("%d
",sum);
    }
}


int main()
{
    freopen("input.txt", "r",stdin);
    char ch;
    int  i, j;
    scanf("%d%*c", &n);
    for(i=0; i<n; ++i){
        scanf("%c %d %d%*c",&ch,&mat[i][0],&mat[i][1]);
    }
    
    while(gets(str)){
        solve();
    }
    return 0;
}

- 생명의 의 미 는 그 에 게 의 미 를 부여 하 는 데 있다.
오리지널
http://blog.csdn.net/shuangde800
，By D_Double