MCM_Iterative.cpp

#include<iostream>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define PI 2*acos(0.0)
#define SIZE 1000000
#define endl '\n'
int caseno=1;
#define CP() printf("Case %d: ",caseno++)
#define R() freopen("in.txt","r",stdin)
#define W() freopen("out.txt","w",stdout)
#define sfi(_i) scanf("%d",&_i)
#define sfc(_c) scanf("%c",&_c)
#define pf1(_i) cout<<_i
#define pfl() cout<<endl
#define pfs() printf(" ")
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define REV(i,a,b) for(i=(a);i>=(b);i--)
using namespace std;
int MCM(int d[], int n);
int M[10][10], S[10][10];


int main() {
    int i,j,n=5;
    int d[11]={15,10,25,20,5,15};
    FOR(i,0,10)
        FOR(j,0,10)
            M[i][j]=S[i][j]=-1;

    /*
    printf("Input Matrix Numbers: ");
    scanf("%d", &n);
    FOR(i,0,n+1)
        scanf("%d", &d[i]);
    */

    MCM(d,n);

    FOR(i,1,n+1) {
        FOR(j,1,n+1) {
            printf("%5d ",M[i][j]);
        }
        pfl(); pfl();
    }
    pfl(); pfl();
    pf1("\t");
    FOR(i,1,n+1) {
        FOR(j,1,n+1) {
            printf("%2d ",S[i][j]);
        }
        pfl(); pfl(); pf1("\t");
    }

	return 0;
}

int MCM(int d[], int n) {
    int len,i,j,k,temp;
    FOR(i,1,n+1)
        M[i][i]=0;
    for(len=2;len<=n;len++) {
        for(i=1; i<=n-len+1;i++) {
            j=i+len-1;
            M[i][j]=1<<30;
            for(k=i;k<=j-1;k++) {
                temp=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];
                if(temp<M[i][j]){
                    M[i][j]=temp;
                    S[i][j]=k;
                }
            }
        }
    }
}