[TOC]

7-1 矩阵链相乘问题

矩阵的乘法定义如下：设A是m×p的矩阵，B是p×n的矩阵，则A与B的乘积为m×n的矩阵，记作C=AB，其中，矩阵C中的第i行第j列元素cij可以表示为：cij=Σk=1paik×bkj=ai1b1j+ai2b2j+⋯+aipbpj.

当多个矩阵相乘时，采用不同的计算顺序所需的乘法次数不相同。例如，A是50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵，
计算ABC有两种方式：(AB)C和A(BC)，前一种需要15000次乘法计算，后一种则只需3500次。

设A1,A2,…,An为矩阵序列，Ai是阶为Pi−1∗Pi的矩阵(1≤i≤n)。试确定矩阵的乘法顺序，使得计算A1A2…An过程中元素相乘的总次数最少。

输入格式:

每个输入文件为一个测试用例，每个测试用例的第一行给出一个正整数n(1≤n≤500)，表示一共有n个矩阵A1,A2,…,An，第二行给出n+1个整数P0,P1…Pn，以空格分隔，其中1≤Pi≤100(0≤i≤n)，第i个矩阵Ai是阶为Pi−1∗Pi的矩阵。

输出格式:

获得上述矩阵的乘积，所需的最少乘法次数。

输入样例:

在这里给出一组输入。例如：

1
2
5
30 35 15 5 10 20

输出样例:

在这里给出相应的输出。例如：

1
11875

算法步骤：

1.初始化一个二维数组m，大小为n*n；

2.对于i=1到n，设置m[i]_[i]=0，即对角线上的元素置零;

3.自底到上、自左到右对对角线右边的空位进行填表，计算m[i]_[j]；

4.根据状态转移方程更新数组m；

5.最终m[1]_[n]即为最少数乘次数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
using namespace std;
int n;
int p[10000];
//因为可相乘矩阵要求RA=CB，所以p[i-1]代表矩阵行数，p[i]代表矩阵列数
int m[10000][10000];//数组m记录Ai···Aj所需的最少数乘次数
//int s[10000][10000];数组s用于记录最优断开位置

int MatrixChain(){
    for(int i=1;i<=n;i++)
        m[i][i]=0;//对角线元素计为0，因为i=j时只有一个矩阵，无需乘法
    for(int i=n;i>=1;i--){//自底而上填表
        for(int j=i+1;j<=n;j++){
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//更新最小数乘次数
            //s[i][j]=i;当前最优断点为i
            for(int k=i+1;k<j;k++){
            //寻找最优次序中的断开位置，范围是i+1到j-1，因为这个断开位置既不会
            是第一个矩阵也不会是最后一个矩阵
                int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                //p[i-1]*p[k]*p[j]是Ai···Ak与Ak+1···Aj的数乘次数
                if(t<m[i][j]){
                    m[i][j]=t;//如果当前值更优，更换m[i][j]
                    //s[i][j]=k;更换最优断点
                }
            }
        }
    }
    return m[1][n];
}
int main(){
    cin>>n;
    for(int i=0;i<n+1;i++){
        cin>>p[i];
    }
    int result=MatrixChain();
    cout<<result;
    return 0;
}

7-2 最大k乘积

设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。

如3*12=26

31*2=62

此时最优解为62

输入格式:

第1 行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的段数。
接下来的一行中是一个n位十进制整数。（n<=10）

输出格式:

计算出的最大k乘积

输入样例1:

1
2
4 3
3456

输出样例1:

1
1020

输入样例2:

1
2
2 1
15

输出样例2:

1
15

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[15][15];

char numstr[15];
int num[15];

int getValue(int i,int j){
    int sum = 0;
    for(int k = i;k < j;k++){
        sum += num[k];
        sum *= 10;
    }
    return sum + num[j];
}

void dpAlgo(int l,int k){
    for(int i = 1;i <= l;i++)
        dp[i][1] = getValue(1,i);
    for(int i = 0;i <= l;i++){
        for(int j = 2;j <= k;j++){
            int temp = 0;
            for(int d = 1;d < i;d++)
                temp = max(temp,dp[d][j - 1] * getValue(d + 1,i));
            dp[i][j] = temp;
        }
    }
}

int main()
{
    int l,k;
    cin >> l >> k >> numstr;//输入长度l、分割段数k、字符串序列
    for(int i = 0;i < l;i++)
        num[i + 1] = numstr[i] - '0';//去掉空字符，将字符串转化成整数数组
    dpAlgo(l,k);
    cout << dp[l][k];
    return 0;
}