MCM_Recursive.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;

class T {
public:
	template<class X> static inline X Sq(X a) {return a*a;}
	template<class X>static inline X Abs(X a) {return a>0 ? a : a*(-1);}
	template<class X>static inline X Max(X a, X b) {return a>b? a:b;}
	template<class X>static inline X Min(X a, X b) {return (a<b)? a:b;}
	template<class X>static inline X Swap(X &a,X &b) {X c=a; a=b; b=c;}
	static inline bool isNum(char c) {return (c>=48 && c<=57);}
	static inline bool isAlpha(char c) {return ((c>=97 && c<=122)||(c>=65 && c<=90));}
	static inline bool isUpper(char c) {return (c>=65 && c<=90);}
	static inline bool isLower(char c) {return (c>=90 && c<=122);}
	static inline int Gcd(int a, int b) {return (b==0)?a:Gcd(b,a%b);}
	static inline long long int Fact(int x) {return (x==1)?x:(x*Fact(x-1));}
	static inline long long int Atoi(char *s);
	static inline char toLower(char c) {return isUpper(c)?c+=32:c;}
	static inline char toUpper(char c) {return isLower(c)?c-=32:c;}
};
/*bool P[SIZE];
void primeSieve() {
	for(int i=0;i<=SIZE;i++) P[i]=1;
	for(int i=2;i<=SIZE;i++ ) {
        if(P[i]==1) {
            for(int j=2*i;j<=SIZE;j+=i) P[j]=0;
        }
    }
}
*/
inline long long int T::Atoi(char *s) {
    long long int n=0;
    for(int i=0;s[i]!='\0';i++) {
        if(T::isNum(s[i])) {
            n*=10;
            n+=s[i]-48;
        }
    }
    return n;
}

int MCM(int d[], int i, int j);
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,1,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 x=1;
int MCM(int d[], int i, int j){
    int k, temp;
    if(i==j) return 0;
    M[i][j]=1<<30;
    for(k=i;k<=j-1;k++) {
        temp=MCM(d,i,k)+ MCM(d,k+1,j) +d[i-1]*d[k]*d[j];
        if(temp<M[i][j]) {
            M[i][j]=temp;
            S[i][j]=k;
        }
    }
    return M[i][j];
}