Cod sursa(job #3164912)
Utilizator | Breaban Daniel-Vasile BreabanDaniel | Data | 4 noiembrie 2023 19:14:00 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.71 kb |
#include <fstream>
#define MAX 1000000
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
long long int m[503],dp[505][505],i,n,g,cost,j;
int main()
{
fin>>n;
for(int i=1;i<=n+1;i++)
fin>>m[i];
for(int i=1;i<=n;i++)
dp[i][i]=0;
for(int x=1;x<n;x++)
for(int i=1;i<=n-x;i++)
{
j=i+x;
dp[i][j]=MAX;
for(int k=0;k<j-i;k++)
{
if(i+k+1==j)
cost=m[j]*m[i]*m[i+k+2];
else
cost=m[i]*m[j+1]*m[i+k+1];
dp[i][j]=min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+cost);
}
}
fout<<dp[1][n];
}