矩阵乘积
Description
Input
n表示矩阵的个数(<=100)
n+1个数,表示矩阵(<=100)
Output
最小的乘法次数
Sample Input
5
5 10 4 6 10 2
Sample Output
348
解题思路
这道题的动态转移方程:
i为开头,j为末尾,k为中间隔开的位置。
#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[102],b[102],f[102][102],t;
int main()
{
cin>>n;
for(long long i=1;i<=n+1;i++) cin>>a[i];
for(long long i=2;i<=n;i++)
for(long long j=1;j<=n-i+1;j++)
{
f[j][i]=0x7f7f7f7f;//赋初值
for(long long k=1;k<i;k++)
f[j][i]=min(f[j][i],f[j+k][i-k]+f[j][k]+a[j]*a[i+j]*a[j+k]);//动态转移方程
}
cout<<f[1][n];
return 0;
}
谢谢阅读,如有疑惑或发现作者错误请在评论区留言。
本文地址:https://blog.csdn.net/SSL_lyw/article/details/108178926
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的,请 点击进行留言回复,万千网友为您解惑!
网友评论