Pagini recente » Cod sursa (job #729986) | Cod sursa (job #1000536)
#include<stdio.h>
#include<algorithm>
#define INF 1 << 30
#define NMAX 507
#define LL long long
using namespace std;
LL D[NMAX][NMAX], a[NMAX], n;
void dinamic(){
for(int Lung = 2; Lung <= n; ++ Lung)
for(int i = 1; i <= n - Lung + 1; ++ i){
int j = i + Lung - 1;
D[i][j] = INF;
for(int k = i; k <= j - 1; ++ k)
D[i][j] = min(D[i][j], D[i][k] + D[k + 1][j] + a[i - 1] * a[k] * a[j]);
}
}
int main(){
freopen("podm.in", "r", stdin);
freopen("podm.out", "w", stdout);
scanf("%lld", &n);
for(int i = 0; i <= n; ++ i)
scanf("%lld", &a[i]);
dinamic();
printf("%lld", D[1][n]);
return 0;
}