Cod sursa(job #3251321)
| Utilizator | Data | 25 octombrie 2024 18:31:26 | |
|---|---|---|---|
| Problema | Parantezare optima de matrici | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.47 kb |
#include <fstream>
using namespace std ;
ifstream cin("podm.in");
ofstream cout("podm.out");
int n,a[505];
long long dp[502][502] ;
int main()
{
cin>>n;
for(int i=0;i<=n;i++)
cin>>a[i];
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=n;j++){
dp[i][j]=LLONG_MAX ;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i-1]*a[j]*a[k]);
}
}
cout<<dp[1][n];
return 0 ;
}
