零崎的朋友很多Ⅲ(矩阵链相乘)

2016-12-02 12:51:53来源:网络收集作者:Mark人点击

第七城市
零崎的朋友很多Ⅲ
题目描述

零崎有很多朋友,其中有一个叫jhljx。


jhljx大家很熟悉了,他数学不好也是出了名的,大家都懂。


现在jhljx遇到了矩阵乘法,他当时就懵了。数都数不清的他,矩阵乘法怎么可能会算的清楚呢?虽然零崎觉得还不如让你们来算,不过好歹也要给jhljx个面子,给她留下一个证明自己数学实力的机会。为了减小jhljx的计算量,让他赶快算出不正确答案来(估计他算上几遍都不一定能出一个正确答案),零崎请你们帮助jhljx。


输入

多组输入数据。


每组数据以N开始,表示矩阵链的长度。接下来一行N+1个数表示矩阵的行/列数。


1<=N<=300


输出

对于每组样例,输出一行最少运算次数的方案,每两个矩阵相乘都用“()”括起来,详见样例


如果存在多种解决方案,最终输出结果选取先计算左边的矩阵,详见Hint


输入样例

3
10 30 5 60
3
10 20 5 4


输出样例

((A1A2)A3)
((A1A2)A3)


Hint

对于输入的第二组数据,


如果计算顺序为((A1A2)A3),结果为10×20×5 + 10×5×4= 1200,


如果计算顺序为A1(A2A3), 结果为20×5×4 + 10×20×4 = 1200


那么输出结果选取第一个


题目解析

弄懂这三点,这个问题就迎刃而解了:
(1) 矩阵链A1,A2,…,An相乘的算法,状态转移方程:
m[i][j] = min { m[i][k] + m[k+1][j] + pi-1*pk*pj | i<=k< j };
(2) 如果存在多种解决方案,最终输出结果选取先计算左边的矩阵:
代码中的这一句:“m[i][j] >= temp”,“=”不能少。
(3) 打印出最少相乘次数对应的结果。这就要求我们必须使用一个数组divPos[][]保存分点位置(divPos[i][j]表示Ai~Aj之间的分点位置)。然后再根据记录的分点,使用递归进行打印。
递归伪代码:
printResult(int left, int right)
if(left == right)
print Aleft;
else
print“(”;
printfResult(left, divPos[left][right]);
printResult(divPos[left][right]+1, right);
print “)”;


代码如下#include
#include
#include
#include
#define INF 0xFFFFFF;
using namespace std;
int divPos[505][505];
int p[505];
int m[505][505];
void printResult(int i, int j)
{
if(i == j)
printf("A%d", i);
else
{
printf("(");
printResult(i, divPos[i][j]);
printResult(divPos[i][j] + 1, j);
printf(")");
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
getchar();
for(int i = 0; i <= n; i++)
scanf("%d", &p[i]);
getchar();
for(int i = 0; i <= n; i++)
m[i][i] = 0;
for(int len = 2; len <= n; len++)
for(int i = 1; i <= n - len + 1; i++)
{
int j = i + len -1;
m[i][j] = INF;
for(int k = i; k < j; k++)
{
int temp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(m[i][j] >= temp)
{
m[i][j] = temp;
divPos[i][j] = k;
}
}
}
printResult(1, n);
printf("/n");
}
}
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台