Cod sursa(job #2553690)
Utilizator | Barbu Alexandru cyg_Alex_codegician | Data | 22 februarie 2020 11:06:01 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <fstream>
using namespace std;
ifstream fin ("podm.in");
ofstream fout ("podm.out");
int main()
{
int n,lg[505];
fin >> n;
for (int i=0;i<=n;i++)
{
fin >> lg[i];
}
long long dp[505][505],minn;
int j;
for (int i=1;i<=n;i++)
{
dp[i][i]=0;
}
for (int d=1;d<=n-1;d++)
{
for (int i=1;i<=n-d;i++)
{
j=i+d;
minn=1e18;
for (int k=i;k<=j-1;k++)
{
long long x=dp[i][k]+dp[k+1][j]+lg[i-1]*lg[k]*lg[j];
if (x<minn)
minn=x;
}
dp[i][j]=minn;
}
}
fout << dp[1][n];
}