太浪费时间了！~~
就做了简单的测试 没考虑太多的特殊情况
注释就写这么多了 不能在这个东西上浪费太多时间~~

#include <malloc.h>
#include <stdio.h>

int Right(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode);

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历左子树
// 输入参数 : int & nSum 计算量
// 输入参数 : int & nPos 遍历矩阵的位置
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int arrDepth[] 各个矩阵元素的所在二叉树深度
// 输入参数 : int nDepth 当前深度
// 输入参数 : int & nNode 节点数
// 返 回 值 : int 矩阵行数
// 作者信息 : 指手画脚 2010-1-11 12:32:47
/////////////////////////////////////////////////////////////////////////////
int Left(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode)
{
    nNode++;    // 记录节点数
    
    int nLeft = 0;        // 第一个矩阵的行
    int nRight = 0;        // 第二个矩阵的列
    nDepth++;    // 记录深度

    // 判断当前深度是否超过给定深度
    if (nDepth > arrDepth[nPos])
        return -1;

    // 判读是否达到指定深度
    if (nDepth == arrDepth[nPos])
        return arr[nPos++];
    else
        nLeft = Left(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nLeft)
        return -1;

    // 向右子树遍历
    nRight = Right(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nRight)
        return -1;

    // 计算计算量
    nSum += nLeft*nRight;    
    return nLeft;
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历右子树
// 输入参数 : int & nSum 计算量
// 输入参数 : int & nPos 遍历矩阵的位置
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int arrDepth[] 各个矩阵元素的所在二叉树深度
// 输入参数 : int nDepth 当前深度
// 输入参数 : int & nNode 节点数
// 返 回 值 : int 矩阵列数
// 作者信息 : 指手画脚 2010-1-11 12:33:48
/////////////////////////////////////////////////////////////////////////////
int Right(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode)
{
    nNode++;    // 记录节点数

    int nLeft = 0;        // 第一个矩阵的行
    int nRight = 0;        // 第二个矩阵的列
    nDepth++;    // 记录深度

    // 判断当前深度是否超过给定深度
    if (nDepth > arrDepth[nPos])
        return -1;
    if (nDepth == arrDepth[nPos])
        return arr[++nPos];
    else
        nLeft = Left(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nLeft)
        return -1;

    // 继续向右子树遍历
    nRight = Right(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nRight)
        return -1;

    // 计算计算量
    nSum += nLeft*nRight;
    return nRight;
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 计算矩阵在当前满二叉树下的计算量
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int nLen 数组长度
// 输入参数 : int arrDepth[] 满二叉树深度数组
// 返 回 值 : int 如果计算成功返回计算量，否则返回-1
// 作者信息 : 指手画脚 2010-1-11 12:43:32
/////////////////////////////////////////////////////////////////////////////
int CountSum(int arr[], int nLen, int arrDepth[])
{    
    // 计算计算量
    int nSum = 0;
    int nPos = 0;
    int nDepth = 0;
    int nNode = 0;    
    if (-1 == Left(nSum, nPos, arr, arrDepth, nDepth, nNode))
        return -1;

    // 判断节点数是否为合法满二叉树
    if (2*nLen-3 != nNode)
        return -1;    
    // 计算成功，返回计算量
    return nSum;
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 递归生成所有可能的满二叉树
// 输入参数 : int n 深度数组标记
// 输入参数 : int arrDepth[] 满二叉树的深度数组
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int nLen 矩阵数组长度
// 输入参数 : int & nMin 计算量最小值
// 输入参数 : int arrMinDepth[] 计算量最小值时的深度数组
// 作者信息 : 指手画脚 2010-1-11 12:50:02
/////////////////////////////////////////////////////////////////////////////
void EnumTree(int n, int arrDepth[], int arr[], int nLen, int & nMin, int arrMinDepth[])
{
    // 判断是否已经生成完成一组深度数组
    if (-1 == n)
    {// 完成一组深度数组
        // 计算计算量
        int nSum = CountSum(arr, nLen, arrDepth);
        // 判断是否为最小计算量
        if (-1 != nSum && (nSum < nMin || 0 == nMin))
        {
            for (int i=0; i<nLen-1; i++)
                arrMinDepth[i] = arrDepth[i];
            nMin = nSum;
        }        
        return;
    }
    // 从小到大设置当前深度
    for (int i=2; i<nLen; i++)
    {
        arrDepth[n] = i;
        EnumTree(n-1, arrDepth, arr, nLen, nMin, arrMinDepth);
    }
}

void Expreesion_Right(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth);
/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历左子树求求表达式
// 输入参数 : char sz[] 表达式保存字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 输入参数 : int & nSzPos 当前字符串位置
// 输入参数 : int & nPos 遍历深度的位置
// 输入参数 : int arrDepth[] 深度数组
// 输入参数 : int nDepth 当前深度
// 作者信息 : 指手画脚 2010-1-11 13:37:53
/////////////////////////////////////////////////////////////////////////////
void Expreesion_Left(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth)
{
    if (nMaxLen < nSzPos)
        return;
    nDepth++;
    if (nDepth == arrDepth[nPos])
    {    
        nPos++;
        sz[nSzPos++] = 'A';
        sz[nSzPos++] = nPos+'0';
        return;
    }
    sz[nSzPos++] = '(';
    Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    Expreesion_Right(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    sz[nSzPos++] = ')';
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历右子树求求表达式
// 输入参数 : char sz[] 表达式保存字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 输入参数 : int & nSzPos 当前字符串位置
// 输入参数 : int & nPos 遍历深度的位置
// 输入参数 : int arrDepth[] 深度数组
// 输入参数 : int nDepth 当前深度
// 作者信息 : 指手画脚 2010-1-11 13:37:50
/////////////////////////////////////////////////////////////////////////////
void Expreesion_Right(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth)
{
    if (nMaxLen < nSzPos)
        return;
    nDepth++;
    if (nDepth == arrDepth[nPos])
    {    
        nPos++;
        sz[nSzPos++] = 'A';
        sz[nSzPos++] = nPos+'0';
        return;
    }
    sz[nSzPos++] = '(';
    Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    Expreesion_Right(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    sz[nSzPos++] = ')';
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 生成表达式
// 输入参数 : int arrDepth[] 满二叉树深度数组
// 输入参数 : int nDepthLen 深度数组的长度
// 输入参数 : char sz[] 保存表达式的字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 作者信息 : 指手画脚 2010-1-11 13:01:29
/////////////////////////////////////////////////////////////////////////////
void GetExpreesion(int arrDepth[], int nDepthLen, char sz[], int nMaxLen)
{
    int nPos = 0;
    int nSzPos = 0;
    Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, 0);
}

int main()
{
    // 测试样本
    int n = 7;
    int* pArr = (int*)malloc(sizeof(int)*n);
    if (NULL == pArr)
        return 1;
    int* pDepth = (int*)malloc(sizeof(int)*n);
    if (NULL == pDepth)
        return 1;
    int* pMinDepth = (int*)malloc(sizeof(int)*n);
    if (NULL == pMinDepth)
        return 1;    
    pArr[0] = 30;
    pArr[1] = 35;
    pArr[2] = 15;
    pArr[3] = 5;
    pArr[4] = 10;
    pArr[5] = 20;
    pArr[6] = 25;    

    int nMin = 0;

    // 求最简计算量
    EnumTree(n-1, pDepth, pArr, n, nMin, pMinDepth);// 1300
    char sz[1024] = "";
    GetExpreesion(pMinDepth, n-1, sz, 1024);
    printf("最小计算量计算方法：%s\n", sz);

    // free
    free(pArr);
    pArr = NULL;
    free(pDepth);
    pDepth = NULL;
    free(pMinDepth);
    pMinDepth = NULL;

    return 0;
}

我也拿题去看看！看了再说！

你能给个你的测试结果?

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

我这里输出正常啊 就是你题目中的那个例子 可以正确输出
其他的我也试了 没问题的

我等会来check 你的code.

现在公司有事情。。

Hi,指手画脚:

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

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

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

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

Thanks

#include <malloc.h>
#include <stdio.h>

int Right(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode);

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历左子树
// 输入参数 : int & nSum 计算量
// 输入参数 : int & nPos 遍历矩阵的位置
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int arrDepth[] 各个矩阵元素的所在二叉树深度
// 输入参数 : int nDepth 当前深度
// 输入参数 : int & nNode 节点数
// 返 回 值 : int 矩阵行数
// 作者信息 : 指手画脚 2010-1-11 12:32:47
/////////////////////////////////////////////////////////////////////////////
int Left(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode)
{
    nNode++;    // 记录节点数
    
    int nLeft = 0;        // 第一个矩阵的行
    int nRight = 0;        // 第二个矩阵的列
    nDepth++;    // 记录深度

    // 判断当前深度是否超过给定深度
    if (nDepth > arrDepth[nPos])
        return -1;

    // 判读是否达到指定深度
    if (nDepth == arrDepth[nPos])
        return arr[nPos++];
    else
        nLeft = Left(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nLeft)
        return -1;

    // 向右子树遍历
    nRight = Right(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nRight)
        return -1;

    // 计算计算量
    nSum += nLeft*nRight;    
    return nLeft;
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历右子树
// 输入参数 : int & nSum 计算量
// 输入参数 : int & nPos 遍历矩阵的位置
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int arrDepth[] 各个矩阵元素的所在二叉树深度
// 输入参数 : int nDepth 当前深度
// 输入参数 : int & nNode 节点数
// 返 回 值 : int 矩阵列数
// 作者信息 : 指手画脚 2010-1-11 12:33:48
/////////////////////////////////////////////////////////////////////////////
int Right(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode)
{
    nNode++;    // 记录节点数

    int nLeft = 0;        // 第一个矩阵的行
    int nRight = 0;        // 第二个矩阵的列
    nDepth++;    // 记录深度

    // 判断当前深度是否超过给定深度
    if (nDepth > arrDepth[nPos])
        return -1;
    if (nDepth == arrDepth[nPos])
        return arr[++nPos];
    else
        nLeft = Left(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nLeft)
        return -1;

    // 继续向右子树遍历
    nRight = Right(nSum, nPos, arr, arrDepth, nDepth, nNode);
    // 判断是否出现错误遍历
    if (-1 == nRight)
        return -1;

    // 计算计算量
    nSum += nLeft*nRight;
    return nRight;
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 计算矩阵在当前满二叉树下的计算量
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int nLen 数组长度
// 输入参数 : int arrDepth[] 满二叉树深度数组
// 返 回 值 : int 如果计算成功返回计算量，否则返回-1
// 作者信息 : 指手画脚 2010-1-11 12:43:32
/////////////////////////////////////////////////////////////////////////////
int CountSum(int arr[], int nLen, int arrDepth[])
{    
    // 计算计算量
    int nSum = 0;
    int nPos = 0;
    int nDepth = 0;
    int nNode = 0;    
    if (-1 == Left(nSum, nPos, arr, arrDepth, nDepth, nNode))
        return -1;

    // 判断节点数是否为合法满二叉树
    if (2*nLen-3 != nNode)
        return -1;    
    // 计算成功，返回计算量
    return nSum;
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 递归生成所有可能的满二叉树
// 输入参数 : int n 深度数组标记
// 输入参数 : int arrDepth[] 满二叉树的深度数组
// 输入参数 : int arr[] 相容矩阵
// 输入参数 : int nLen 矩阵数组长度
// 输入参数 : int & nMin 计算量最小值
// 输入参数 : int arrMinDepth[] 计算量最小值时的深度数组
// 作者信息 : 指手画脚 2010-1-11 12:50:02
/////////////////////////////////////////////////////////////////////////////
void EnumTree(int n, int arrDepth[], int arr[], int nLen, int & nMin, int arrMinDepth[])
{
    // 判断是否已经生成完成一组深度数组
    if (-1 == n)
    {// 完成一组深度数组
        // 计算计算量
        int nSum = CountSum(arr, nLen, arrDepth);
        // 判断是否为最小计算量
        if (-1 != nSum && (nSum < nMin || 0 == nMin))
        {
            for (int i=0; i<nLen-1; i++)
                arrMinDepth[i] = arrDepth[i];
            nMin = nSum;
        }        
        return;
    }
    // 从小到大设置当前深度
    for (int i=2; i<nLen; i++)
    {
        arrDepth[n] = i;
        EnumTree(n-1, arrDepth, arr, nLen, nMin, arrMinDepth);
    }
}

void Expreesion_Right(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth);
/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历左子树求求表达式
// 输入参数 : char sz[] 表达式保存字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 输入参数 : int & nSzPos 当前字符串位置
// 输入参数 : int & nPos 遍历深度的位置
// 输入参数 : int arrDepth[] 深度数组
// 输入参数 : int nDepth 当前深度
// 作者信息 : 指手画脚 2010-1-11 13:37:53
/////////////////////////////////////////////////////////////////////////////
void Expreesion_Left(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth)
{
    if (nMaxLen < nSzPos)
        return;
    nDepth++;
    if (nDepth == arrDepth[nPos])
    {    
        nPos++;
        sz[nSzPos++] = 'A';
        sz[nSzPos++] = nPos+'0';
        return;
    }
    sz[nSzPos++] = '(';
    Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    Expreesion_Right(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    sz[nSzPos++] = ')';
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 遍历右子树求求表达式
// 输入参数 : char sz[] 表达式保存字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 输入参数 : int & nSzPos 当前字符串位置
// 输入参数 : int & nPos 遍历深度的位置
// 输入参数 : int arrDepth[] 深度数组
// 输入参数 : int nDepth 当前深度
// 作者信息 : 指手画脚 2010-1-11 13:37:50
/////////////////////////////////////////////////////////////////////////////
void Expreesion_Right(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth)
{
    if (nMaxLen < nSzPos)
        return;
    nDepth++;
    if (nDepth == arrDepth[nPos])
    {    
        nPos++;
        sz[nSzPos++] = 'A';
        sz[nSzPos++] = nPos+'0';
        return;
    }
    sz[nSzPos++] = '(';
    Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    Expreesion_Right(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);
    sz[nSzPos++] = ')';
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 生成表达式
// 输入参数 : int arrDepth[] 满二叉树深度数组
// 输入参数 : int nDepthLen 深度数组的长度
// 输入参数 : char sz[] 保存表达式的字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 作者信息 : 指手画脚 2010-1-11 13:01:29
/////////////////////////////////////////////////////////////////////////////
void GetExpreesion(int arrDepth[], int nDepthLen, char sz[], int nMaxLen)
{
    int nPos = 0;
    int nSzPos = 0;
    Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, 0);
}

/////////////////////////////////////////////////////////////////////////////
// 函数说明 : 计算指定矩阵最小计算量表达式
// 输入参数 : int arr[] 矩阵数组
// 输入参数 : int nLen 矩阵数组的长度
// 输入参数 : char sz[] 保存表达式的字符串
// 输入参数 : int nMaxLen 字符串最大长度
// 返 回 值 : BOOL 是否计算成功
// 作者信息 : 指手画脚 2010-1-11 15:52:13
/////////////////////////////////////////////////////////////////////////////
bool GetMinProcess(int arr[], int nLen, char sz[], int nMaxLen)
{
    int* pDepth = (int*)malloc(sizeof(int)*nLen);
    if (NULL == pDepth)
        return false;
    int* pMinDepth = (int*)malloc(sizeof(int)*nLen);
    if (NULL == pMinDepth)
        return false;

    int nMin = 0;

    // 求最简计算量
    EnumTree(nLen-1, pDepth, arr, nLen, nMin, pMinDepth);// 1300    
    GetExpreesion(pMinDepth, nLen-1, sz, 1024);    
    
    // free
    free(pDepth);
    pDepth = NULL;
    free(pMinDepth);
    pMinDepth = NULL;

    return true;
}

int main()
{
    // 测试样本
    int n = 0;
    scanf("%d", &n);
    int* pArr = (int*)malloc(sizeof(int)*n);
    if (NULL == pArr)
        return 1;    

    for (int i=0; i<n; i++)
    {
        printf("第%d个数：", i+1);
        scanf("%d", pArr+i);
    }
    
    char sz[1024] = "";
    if (GetMinProcess(pArr, n, sz, 1024))
        printf("最小计算量计算方法：%s\n", sz);

    // free
    free(pArr);
    pArr = NULL;    

    return 0;
}

可以不

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