Cod sursa(job #2976169)
| Utilizator | Data | 8 februarie 2023 15:55:19 | |
|---|---|---|---|
| Problema | Parantezare optima de matrici | Scor | 70 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
#include<fstream>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
const int N=500, INF=1<<30;
int v[N+2], dp[N][N];
int main()
{
int n;
fin >> n;
for(int i=1; i<=n+1; i++)
fin >> v[i];
for(int i=1;i<=n; i++)
for(int j=1; j<=n; j++)
{
if(i==j)
dp[i][j]=0;
}
for(int i=n; i>=1; i--)
for(int j=i+1; j<=n; j++)
{
dp[i][j]=INF;
for(int k=i; k<j; k++)
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+v[i]*v[k+1]*v[j+1]);
}
fout << dp[1][n];
return 0;
}
