Hi all,


之前的号wxjeacen被封了之后一直也就没露面，公司的事情也比较多。

这里的牛人越来越少了。之前的 StarWin83,貌似也很久都不露面了。

免掉不必要的矫情。

指手画脚，看看你的code 水平。

有兴趣的也可以贴个代码， 希望不要把这个帖子又一度论文水贴。

Question Describe :

第一个问题，也是比较基本的算法问题。

看看你的基本工，跟我彪过code 的vx_works,StarWin83的基本功都是一流的。


N个矩阵相乘，不同的结合方式会有不同的计算复杂度，所谓的计算复杂度也就是计算量。

A1*A2*A3可以加括号，A1*(A2*A3)或者，(A1*A2)*A3结果都一样，但是计算两未必相同。


input sample:

7

30 35 15 5 10 20 25

(Note:7表示一个输入矩阵的个数。A[i-1],A[i]表示矩阵的两维.比如，30 也就是A[0], 35也就是A[1],这两个就表示第一个矩阵是30*35 , A[1], A[2] 表示第2个矩阵是35*15,这N-1个矩阵是相容的。）

output sample:

((A1 (A2 A3 ))((A4 A5 )A6 ))

(Note:这个组合方式出来的结果，所要的计算两是最简的）


解题愉快。

2楼的不是主角。。

真正的主角还没出来回应呢。

算法是code的灵魂， 基本的算法都不会的人，还能写出什么code.

况且从我要求的output的格式来看

不是你会了DP就能解决的。

[ 本帖最后由 Devil_W 于 2010-1-11 00:16 编辑 ]

期待你的code.

期待你的2叉树。

时间不早了。

我明天还要上班。

希望明天可以看到你的code.

解题愉快。

你能给个你的测试结果?

我这里你那个程序什么也没输出。。。

我等会来check 你的code.

现在公司有事情。。

Hi,指手画脚:

你把你的code修成按照我的sample那样的输入跟输出结构。

输出最好别带空格。否则我做diff的时候会check block.

一会我也写个这个程序，我还没写。。。

我会写个脚本生成一些数据。测试你的funtion.以及时空效率。

Thanks

Ok,我的code出来了。

#include<iostream>
#include<climits>
#define MAX 1024
using namespace std;
class MatrixChain{
private:
    int *p;
    int **m,**s;
    const int size;
protected:

public:
    MatrixChain(int n):size(n)
        {
            p=new int[n+1];
            for( int i=0;i<n;i++)
            {
                cin>>p[i];
            }
            m=new int*[n+1];
            s=new int*[n+1];
            for( int i=0;i<n+1;i++)
            {
                m[i]=new int[n+1];
                s[i]=new int[n+1];
            }
        }
    ~MatrixChain(){
        delete[] p;
        for(int i=0;i<size+1;i++)
        {
            delete[] m[i];
            delete[] s[i];
        }
        delete [] m;
        delete [] s;
    }
    void Matrix_Chain_Order()
        {
            int n=size-1;
            for( int i;i <=n;i++)
            {
                m[i][i]=0;
            }
            for( int l=2;l<=n;l++)
            {
                for( int i=1; i<=n-l+1;i++)
                {
                    int j= i+l-1;
                    m[i][j]=INT_MAX;
                    for(int k= i; k<=j-1;k++)
                    {
                        int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                        if(q<m[i][j])
                        {
                            m[i][j]=q;
                            s[i][j]=k;
                        }
                    }
                }
            }
        }
    void Print_Optimal_Parens( int i, int j)
        {
            if( i==j)
            {
                cout<<"A"<<i;
                return ;
            }
            else{
                cout<<"(";
                Print_Optimal_Parens(i,s[i][j]);
                Print_Optimal_Parens(s[i][j]+1,j);
                cout<<")";
            }
        }
};
int main()
{
    int s;
    while(cin>>s && !cin.eof())
    {
        if(s==0)
            break;
        MatrixChain matrix(s);
        matrix.Matrix_Chain_Order();
        matrix.Print_Optimal_Parens(1,s-1);
        cout<<endl;
    }
    return 0;
}

看看这段数据，你的结果是多少。