社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
#include<iostream>
#include<cstring>
using namespace std;
long long a[1002];
long long dp[1002][1002];
int main(){
int n;
cin>>n;
for(int i=0;i<n+1;i++){
cin>>a[i];
}
memset(dp,0x3f,sizeof(dp)); //△
for(int i=1;i<=n;i++){
dp[i][i]=0;
}
for(int l=2;l<=n;l++){//枚举矩阵连乘的长度
for(int i = 1;i+l-1<=n;i++){//枚举矩阵连乘起始的位置
int j =i+l-1;//j为长度为l的链的末尾
for(int k =i;k<=j-1;k++){//枚举分割点
long long q = dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
if(q<dp[i][j])
dp[i][j]=q;
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!