/*
THIS CODE HAS BEEN TESTED AND IS FULLY OPERATIONAL.

Problem Statement: Given sequence k = k1 <k2 < … <kn of n sorted keys, with a search probability pi for each key ki . Build the Binary search tree that has the least search cost given the access probability for each key?

Code from DataStructuresAndAlgorithms (SPPU - Second Year - Computer Engineering - Content) repository on KSKA Git: https://git.kska.io/sppu-se-comp-content/DataStructuresAndAlgorithms/
*/

// BEGINNING OF CODE
#include<iostream>
using namespace std;
#define MAX 10
int find(int,int);
void print(int,int);
int p[MAX],q[MAX],w[10][10],c[10][10],r[10][10],i,j,k,n,m;
char idnt[7][10];

int main()
{
	cout<<"Number of identifiers:\t";
	cin>>n;
	cout<<"Enter identifiers:"<<endl;
	for(i=1;i<=n;i++) {
		cout<<"Identifier "<<i<<":\t";
		cin>>idnt[i];
	}
	cout<<"Enter success probability for identifiers:\n";
	for(i=1;i<=n;i++) {
		cout<<"Identifier "<<i<<":\t";
		cin>>p[i];
	}
	cout<<"Enter failure probability for identifiers:\n";
	for(i=0;i<=n;i++) {
		cout<<"Identifier "<<i<<":\t";
		cin>>q[i];
	}
	cout<<"\n Weight        Cost          Root \n";

	for(i=0;i<=n;i++)
	{
		w[i][i]=q[i];
		c[i][i]=r[i][i]=0;
		cout<<"\n"<<w[i][i]<<"          "<<c[i][i]<<"             "<<r[i][i];
		cout<<"-------------------------------------------------------------------------";
	}
	for(i=0;i<n;i++)
	{
		j=i+1;
		w[i][j]= p[j]+q[i]+q[j]; 	// w(i,j)= p[j]+q[i]+w(i,j-1)
		c[i][j]=q[i]+c[i][j-1]+c[j][j];   // c(i,j)= min { c (i,k-1)+c(k+1, j) }+ w(i,j))
		r[i][j]=j;
		cout<<"\n"<<w[i][j]<<"           "<<c[i][j]<<"              "<<r[i][j];
		cout<<"-------------------------------------------------------------------------";
	}
	for(m=2;m<=n;m++)
	{
		for(i=0;i<=n-m;i++)
		{
			j=i+m;
			w[i][j]=w[i][j-1]+p[j]+q[j];
			k=find(i,j);
			r[i][j]=k;
			c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
			cout<<"\n"<<w[i][j]<<"            "<<c[i][j]<<"           "<<r[i][j];
		}
	}
	cout<<"-------------------------------------------------------------------------";
	cout<<endl<<endl<<"THE FINAL OBST IS:";
	print(0,n);
	return 0;
}
int find(int i,int j)
{
	int min=2000,m,l; //c[i][j];
	for(m=i+1;m<=j;m++)
		if(c[i][m-1]+c[m][j]<min)
		{
			min=c[i][m-1]+c[m][j];
			l=m;
		}
	return l;
}
void print(int i,int j)
{
	if(i<j)
		cout<<"\n"<<idnt[r[i][j]];
	else
		return;
	print(i,r[i][j]-1);
	print(r[i][j],j);
}
// END OF CODE