34 lines
964 B
Java
34 lines
964 B
Java
import java.util.*;
|
|
|
|
public class _11049 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
int N = sc.nextInt();
|
|
int[][] rc = new int[N][2];
|
|
for(int i=0; i<N; i++) {
|
|
rc[i][0] = sc.nextInt();
|
|
rc[i][1] = sc.nextInt();
|
|
}
|
|
sc.close();
|
|
|
|
int[][] dp = new int[N][N];
|
|
|
|
for(int len=2; len<=N; len++) {
|
|
for(int start = 0; start <= N - len ; start++) {
|
|
int end = start + len - 1;
|
|
dp[start][end] = Integer.MAX_VALUE;
|
|
|
|
for(int k=start; k<end; k++) {
|
|
int leftOP = dp[start][k];
|
|
int rightOP = dp[k+1][end];
|
|
int mergeOP = rc[start][0]*rc[k][1]*rc[end][1];
|
|
|
|
dp[start][end] = Math.min(dp[start][end], leftOP + rightOP + mergeOP);
|
|
}
|
|
}
|
|
}
|
|
|
|
System.out.println(dp[0][N-1]);
|
|
}
|
|
}
|