Cod sursa(job #1807120)
Utilizator | Data | 16 noiembrie 2016 00:57:36 | |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,j,k,d[501];
long long dp[501][501];
int main()
{
freopen("podm.in","r",stdin);
freopen("podm.out","w",stdout);
scanf("%d",&n);
for(i=0;i<=n;++i) scanf("%d",&d[i]);
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
{
long long A=1LL<<60;
int D=d[j-i-1]*d[j];
for(k=j-i;k<j;++k)
A=min(A,dp[j-i][k]+dp[k+1][j]+1LL*D*d[k]);
dp[j-i][j]=A;
}
printf("%lld ",dp[1][n]);
return 0;
}