Cod sursa(job #2348517)
Utilizator | Buzatu Bogdan Mihai Bogdan_Buzatu | Data | 19 februarie 2019 19:45:29 |
---|---|---|---|
Problema | Parantezare optima de matrici | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
using namespace std;
ifstream fin("podm.in");
ofstream fout("podm.out");
long long d[510][510],n,v[510];
int main(){
fin>>n;
n++;
for(int i=1; i<=n; i++){
fin>>v[i];
}
for(int l=2;l<=n;l++){
for(int i=1; i+l-1<=n;i++){
int j=i+l;
d[i][j]=2000000000000000;
for(int k=i+1; k<j; k++){
d[i][j]=min(d[i][j], d[i][k]+d[k][j]+v[i]*v[j]*v[k]);
}
}
}
fout<<d[1][n];
}