【SSL】矩阵乘积
程序员文章站
2022-06-16 09:21:54
矩阵乘积DescriptionInputn表示矩阵的个数(<=100)n+1个数,表示矩阵(<=100)Output最小的乘法次数Sample Input55 10 4 6 10 2Sample Output348解题思路这道题...
矩阵乘积
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
下一篇: 冒泡排序