注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[1003] nbut 矩阵链乘法  

2012-11-01 22:10:28|  分类: NBUT OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
用的是DP。要求矩阵相乘的最少次数。
用二维数组m[ i ][ j ]储存最佳计算次序对应的乘法次数,用p[n]存储矩阵的长和宽。

DP基本语句:m[i][k] + m[k + 1][j] + p[i - 1] * p[j] * p[k];

题目:

  • [1003] 矩阵链乘法

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 给定一个有n个矩阵的矩阵链A1A2A3…An,其中矩阵Ai(i=1,2,3…n)的维度为pi-1*pi。我们知道,两个维度分别为m*r和r*n的矩阵用一般的矩阵乘法相乘,所需的运算次数为m*r*n,最后得到一个维度为m*n的结果矩阵。对于矩阵链问题,因为矩阵乘法具有结合律,其运算顺序有很多中选择。换句话说,不论如何括号其乘积,最后结果都会是一样的。例如,若有四个矩阵A、B、C和D,将可以有:

    (ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ... 

    但括号其乘积的顺序会影响到需要计算乘积所需简单算术运算的数目,即其效率。例如,设A为一10*30矩阵,B为30*5矩阵与C为5*60矩阵,则:

    (AB)C有(10*30*5) + (10*5*60) = 1500 + 3000 = 4500 个运算 A(BC)有(30*5*60) + (10*30*60) = 9000 + 18000 = 27000 个运算 ... 

    明显地,第一种方式要有效多了。所以,矩阵链乘法问题也就是如何对矩阵乘积加括号,使得它们的乘法次数达到最少。


  • 输入
  • 输入的第一行为一个正整数n(1<=n<=200)。表示矩阵的个数。
    输入的第二行包含n+1个整数,分别表示pi(0<=i<=n),其中每个pi在[1,200]范围内。
  • 输出
  • 输出一个整数表示最少要进行的乘法次数。
  • 样例输入
  • 3 1 2 3 4 3 10 30 5 60 
  • 样例输出
  • 18 4500 
  • 提示
  • 来源
  • Timebug

代码:

#include<iostream>
using namespace std;

int p[201];
int m[201][201],s[201][201];

void Matrix(int *p,int n,int m[][201],int s[][201])
{
for(int i = 0;i < n;i ++)
{
m[i][i] = 0;
s[i][i] = 0;
}
for(int r = 2;r <= n;r ++)
for(int i = 1;i <= n - r + 1;i ++)
{
int j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i - 1] * p[j] * p[i];
s[i][j] = i;
for(int k = i + 1;k < j;k ++)
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[j] * p[k];
if(t < m[i][j])
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}

int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i = 0;i <= n;i ++)
scanf("%d",&p[i]);
Matrix(p,n,m,s);
/*
for(int i = 0;i <= n;i ++)
{
for(int j = 0;j <= n;j ++)
{
cout<<m[i][j];
}
cout<<endl;
}
for(int i = 0;i <= n;i ++)
{
for(int j = 0;j <= n;j ++)
{
cout<<s[i][j];
}
cout<<endl;
}
*/
cout<<m[1][n]<<endl;

}
}




/*
样例输入
3
1 2 3 4
3
10 30 5 60
样例输出
18
4500*/




  评论这张
 
阅读(386)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018