欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

【SSL】矩阵乘积

程序员文章站 2022-06-16 09:21:54
矩阵乘积DescriptionInputn表示矩阵的个数(<=100)n+1个数,表示矩阵(<=100)Output最小的乘法次数Sample Input55 10 4 6 10 2Sample Output348解题思路这道题...

矩阵乘积


Description

【SSL】矩阵乘积

Input

n表示矩阵的个数(<=100)
n+1个数,表示矩阵(<=100)

Output

最小的乘法次数

Sample Input

5
5 10 4 6 10 2

Sample Output

348

解题思路

这道题的动态转移方程:
c[j][i]=min(c[j][i],c[j+k][ik]+c[j][k]+a[j]a[i+j]a[j+k]);c[j][i]=min(c[j][i],c[j+k][i-k]+c[j][k]+a[j]*a[i+j]*a[j+k]);
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

相关标签: 动态规划