poj1651 最优矩阵乘法动态规划解题

题目描述:

有若干个矩阵{Ai},元素都为整数且已知矩阵大小。

如果要计算所有矩阵的乘积A1 * A2 * A3 .. Am,最少要多少次整数乘法?

输入
第一行一个整数n(n <= 100),表示一共有n-1个矩阵。
第二行n个整数B1, B2, B3... Bn(Bi <= 100),第i个数Bi表示第i个矩阵的行数和第i-1个矩阵的列数。
等价地,可以认为第j个矩阵Aj(1 <= j <= n - 1)的行数为Bj,列数为Bj+1。
输出
一个整数,表示最少所需的乘法次数
采用动态规划分析:
优化目标是基本运算次数最小化,而这道题关键在于确定一个乘法的次序,相当于在n个矩阵间加括号。如何界定子问题的边界是产生的问题。如果从前向后划分,所产生的子问题只有后边界,但是在计算子问题A1.....j的过程中,我们需要知道子问题A1....i和子问题A(i+1)....j的信息,所以问题需要前后两个边界。用m[i][j]表示乘积Ai....j所用的最小运算次数。假定最后一次相乘发生在Ai.....k和A(k+1).....j之间,那么m[i][j]=min(i≤k<j){m[i][k]+m[k+1][j]+B(i-1)*B(k)*B(j)};
下边是代码的c语言实现
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX=;
int m[][MAX];
int dp(int *p,int n){
for(int r=;r<=n;r++){
for(int i=;i<=n-r+;i++){
int j=i+r-;
m[i][j]=m[i+][j]+p[i-]*p[i]*p[j];
for(int k=i+;k<=j-;k++){
int t= m[i][k]+m[k+][j]+p[i-]*p[k]*p[j];
if(t<m[i][j]){
m[i][j]=t;
}
}
}
}
return m[][n];
}
int main(){
int n;
scanf("%d",&n);
memset(m,,sizeof(m));
int p[];    
for(int i=;i<n;i++){
scanf("%d",p+i);
}
int res=dp(p,n-);
printf("%d\n",res);
return ;
}

算法时间复杂度为O(n3)。

上一篇:当元素的样式为display:none时获取他的宽高


下一篇:HDOJ-ACM1021(JAVA)