Sample Codes

Knuth Optimization ( Uva 10304 )

 * Bidhan Roy
 * University of Dhaka
 * Problem : Uva - 10304 Optimal Binary Search Tree

#include <cstdio>

#define mx 260
#define inf 1<<28

int a[mx];

int dp[mx][mx]; /// contains the optimal costs of intervals
int p[mx][mx]; /// contains the points by partitioning where we can get minimum cost
int sum[mx]; /// contains cumulative sum of the array

int main(){
	int n;
	while( scanf("%d",&n)==1 ){
		for(int i=0; i<n; i++) {
			if(i) sum[i]+=sum[i-1];
		for(int L=1; L<=n; L++){
			for(int i=0; i<n; i++){
				int j=i+L-1;
				if(L==1) dp[i][j]=0, p[i][j]=i; /// if the length is 1, there is only one possible index
					for(int k=p[i][j-1]; k<=p[i+1][j]; k++) {
						/// optimal point of interval [i,j] will be between 
						/// the optimal points of intervals
						/// [i,j-1] and [i+1,j]
						int cost=0;
						/// 'cost' contains the cost of interval [i,j] if the partition was made
						/// at index 'k'
							dp[i][j]=cost, p[i][j]=k; /// if 'k' is optimal for now, then store it in p[i][j]
	return 0;

Go Back

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s