Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1245
Given a set S = (e1, e2, ..., en) of n distinct elements such that e1 < e2 < . . . < en and considering a binary search tree (see the previous problem) of the elements of S, it is desired that higher the query frequency of an element, closer will it be to the root. The cost of accessing an element ei of S in a tree (cost(ei)) is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of S, (f(e1), f(e2), . . . , f(en)), we say that the total cost of a tree is the following summation: f(e1) ∗ cost(e1) + f(e2) ∗ cost(e2) + . . . + f(en) ∗ cost(en) In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of S. Because of this, it is called the Optimal Binary Search Tree. Input The input will contain several instances, one per line. Each line will start with a number 1 ≤ n ≤ 250, indicating the size of S. Following n, in the same line, there will be n non-negative integers representing the query frequencies of the elements of S: f(e1), f(e2), . . . , f(en), 0 ≤ f(ei) ≤ 100. Input is terminated by end of file. Output For each instance of the input, you must print a line in the output with the total cost of the Optimal Binary Search Tree.
Sample Input 1 5 3 10 10 10 3 5 10 20
Sample Output 0 20 20
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
/*
Knuth Speedup says that the optimal root for a problem i < m < t, where optimal(x,y) is the optimal root between x and y then
optimal(i, j) lies between optimal(i,m-1) to optimal(m+1,j) <- use an index table to store optimal root
Simplify: the optimal root of a problem lies between the optimal root of its sub-problem.
This only applies if the Quadrangle Inequality property is satisfied
*/
int dp[251][251]; // state: left, right
int optimal[251][251]; // optimal root index table for knuth optimization
int sum[251]; // for acquiring range sum between left, right
int n, v;
int main() {
while(scanf("%d",&n) != EOF) {
memset(sum, 0, sizeof sum);
memset(optimal, 0, sizeof dp);
for(int i=0;i i+It n;i++){
scanf("%d", sum+i+1);
sum[i+1] += sum[i];
optimal[i][i] = i;
dp[i][i] = 0;
}
for(int len=1;len i+It n;len++){
for(int i=0;i+len i+It n;i++){
int j = i+len;
// knuth optimization
dp[i][j] = 1e7;
for(int m=optimal[i][j-1]; m < =optimal[i+1][j];m++){
int left_cost = dp[i][m-1] + sum[m] - sum[i];
int right_cost = dp[m+1][j] + sum[j+1] - sum[m+1];
int total_cost = left_cost + right_cost;
if(total_cost < dp[i][j]) {
dp[i][j] = total_cost;
optimal[i][j] = m;
}
}
}
}
printf("%d\n", dp[0][n-1]>;
}
}Input
3 10 10 10
3 5 10 20
Output
20
20
Demonstration
UVA Online Judge solution - 10304 - Optimal Binary Search Tree - UVA Online Judge solution in C,C++,java