Cod sursa(job #2493321)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 16 noiembrie 2019 11:37:00
Problema Parantezare optima de matrici Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

typedef long long lint;

ifstream fin("podm.in");
ofstream fout("podm.out");

lint d[514];
lint dp[514][514];

lint ca(int i, int j, int k){
	return dp[i][k] + dp[k+1][j] + d[i-1]*d[k]*d[j];
}

void sugondese(int i, int j){
	lint mini = ca(i,j,i);
	for(int k = i+1; k <= j-1; k++){
		mini = min(mini, ca(i,j,k));
	}
	dp[i][j] = mini;
}

int main(){
	int n;
	fin >> n;
	for(int i = 0; i < n+1; i++){
		fin >> d[i];
	}
	
	for(int i = 2; i <= n; i++){
		for(int i1 = 1, j1 = i; j1 <= n; i1++, j1++){
			sugondese(i1,j1);
		}
	}
	fout << dp[1][n];
	return 0;
}