Time Limit:1000MS Memory Limit:65536K
Total Submit:5 Accepted:0

Description

两个矩阵A和B相乘的条件是A的列数等于B的行数。若A是一个i*k矩阵，B是一个k*j矩阵，则其乘积C=AB是一个i*j矩阵。我们知道要经过i*k*j次数乘得到C。

由于矩阵乘法满足结合律，在计算一个大于2个矩阵的乘法时有多种乘法策略。打个比方，X，Y和Z都是矩阵，我们要求XYZ。我们可以计算(XY)Z或者X(YZ).假如X是一个5*10的矩阵，Y是一个10*20的矩阵，Z是一个20*35的矩阵。我们来看下这两种不同的乘法，要经过多少次数乘得到要得到的矩阵。

(XY)Z

1. 5*20*10=1000次数乘，得到(XY)的乘积，它是一个5*20的矩阵。
2. 5*35*20=3500次数乘，得到最后要求的矩阵。
3. 总共用了4500次数乘。

X(YZ)
1. 10*35*20=7000次数乘，得到(YZ)的乘积，它是一个10*35的矩阵。
2. 5*35*10=1750次数乘，得到最后要求的矩阵。
3. 总共用了8750次数乘。

我们清楚地发现用(XY)Z能用较少的数乘得到最后结果。
现在，给你一串要乘得矩阵序列A1，A2,...,An.让你决定一种乘法策略得到A1A2...An相乘的结果，所使用的数乘的次数最少。

Input

第一行有一个正整数n(n<11)，表示有n个矩阵。接着有n行，每行有2个正整数(都不大于1000)，表示一个矩阵的行和列。这n行对应A1,A2,...,An.
有多组测试数据。

Output

对于每组测试数据，输出得到A1A2...An相乘结果，所使用最少的数乘的次数。

Sample Input

3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25

Sample Output

105
4500
15125

嗯,想说明何种问题

我是迷途的小羔羊 希望寻找出路

[此贴子已经被作者于2007-11-2 13:29:03编辑过]

#include <iostream>
using namespace std;
int main()
{
int n,i,j,sum,k,p,t1;
while(cin>>n&&n<11)
{
int a[n][2];
for(i=0;i<n;i++)
for(j=0;j<2;j++)
cin>>a[i][j];
sum=0;
while(n!=1)
{
k=a[0][0]*a[1][1];
t1=0;
for(i=1;i<n-1;i++)
{
p=a[i][0]*a[i+1][1];
if(p<k)
{
k=p;
t1=i;
}
}
sum+=a[t1][0]*a[t1][1]*a[t1+1][1];
a[t1][1]=a[t1+1][1];
for(i=t1+1;i<n-1;i++)
{
for(j=0;j<2;j++)
a[i][j]=a[i+1][j];
}
a[n-1][0]=0,a[n-1][1]=0;
n--;
}
cout<<sum<<endl;
}
return 0;
}

这个算法对吗？
感觉能实现 但提交是Wrong Answer

DP,我在C++版看到了一个,他写的不错.
稍微改下就可以提交了.

他的不行把

[此贴子已经被作者于2007-11-2 13:29:35编辑过]

http://bbs.bc-cn.net/viewthread.php?tid=179964&star=at#

动态规划,以前看过一篇文章就是以这道题为例的

是吗？

[此贴子已经被作者于2007-11-2 13:29:58编辑过]