Problem

矩阵链乘问题

输入：

共两行

第一行 N （ 1<=N<=100 ），代表矩阵个数。

第二行有 N+1 个数，分别为 A1 、 A2 ...... An+1 （ 1<=Ak<=2000）， Ak 和 Ak+1 代表第 k 个矩阵是个 Ak X Ak+1 形的。

输出：

共两行

第一行 M ，为最优代价。注：测试用例中 M 值保证小于 2^31

第二行为最优顺序。如 (A1((A2A3)A4)) ，最外层也加括号。

注意:测试用例已经保证了输出结果唯一,所以没有AAA的情况.

测试输入

6
30 35 15 5 10 20 25

测试输出

15125
((A1(A2A3))((A4A5)A6))

Ac code

//
//  main.cpp
//  矩阵连乘
//
//  Created by jetviper on 2017/3/18.
//  Copyright © 2017年 awlsx. All rights reserved.
//

#include <iostream>
#include <stdlib.h>
#include <string.h>
#define INTMAX 214748364
#define Mrx 999
int m[Mrx];
int d[999][999];
int rek[999][999];

int dp(int n){
    int len;
    for (len = 1; len < n; len++)
    {
        
        for (int i = 1, j = i+len; j < n; i++, j++)
        {
            int min = INTMAX;
            for (int k = i; k < j; k++)
            {
                int count = d[i][k] + d[k+1][j] + m[i-1] * m[k] * m[j];
                
                if (count < min)
                {
                    min = count;
                    
                    rek[i][j]=k;
                }
            }
            d[i][j] = min;
        }
    }
    return d[1][n-1];
    
}
int Traceback(int i,int j)
{
    if(i==j) return 1;
    printf("(");
    if (Traceback(i,rek[i][j])){
        if (i == rek[i][j]) {
            printf("A%d",i);
        }
    }
    if(Traceback(rek[i][j]+1,j)){
        if (j == rek[i][j]+1) {
            printf("A%d",j);
        }
    }
    
    printf(")");
    return 0;
}
int main() {
    int n;
    scanf("%d",&n);

    for(int i=0;i<=n;i++){
        scanf("%d",&m[i]);
    }
    printf("%d\n", dp(n+1));
    
    if (n==1) {
        printf("(A1)");
    }else{
    Traceback(1, n);
    }
    printf("\n");
    return 0;
}