Cod sursa(job #1804898)
Utilizator | Mihai Radovici NinjaCube | Data | 13 noiembrie 2016 11:02:23 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <fstream>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
int n,i,j,k,d[501];
long dp[501][501];
int main()
{
fin>>n;
for(i=0;i<=n;++i) fin>>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;
}
fout<<dp[1][n];
return 0;
}