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++) {
			scanf("%d",&a[i]);
			sum[i]=a[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
				else{
					dp[i][j]=inf;
					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+=dp[i][k-1];
						cost+=dp[k+1][j];
						cost+=sum[j]-sum[k];
						cost+=sum[k-1]-(i?sum[i-1]:0);
						/// 'cost' contains the cost of interval [i,j] if the partition was made
						/// at index 'k'
						if(cost<dp[i][j]) 
							dp[i][j]=cost, p[i][j]=k; /// if 'k' is optimal for now, then store it in p[i][j]
					}
				}
			}
		}
		printf("%d\n",dp[0][n-1]);
	}
	return 0;
}

Go Back

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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