Cod sursa(job #3149956)
Utilizator | Data | 13 septembrie 2023 20:45:23 | |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("podm.in");
ofstream g("podm.out");
int const inf=1e9;
int n,i,j,k,a[505],dp[505][505],mi;
int main()
{
f>>n;
for(i=0;i<=n;++i) f>>a[i];
for(i=1;i<=n;++i)
for(j=1;j<=n;++j) dp[i][j]=inf;
for(i=1;i<n;++i){
dp[i][i+1]=a[i-1]*a[i]*a[i+1];
dp[i][i]=0;
}
dp[n][n]=0;
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
for(k=i;k<j;++k){
dp[i][j]=min(dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j] , dp[i][j]);
}
cout<<dp[1][n];
return 0;
}