最优二叉查找树 动态规划法.txt

ACM资料大集合

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//最优二叉查找树  动态规划法
/*
输入：
4
0.1 0.2 0.4 0.3

输出：
1.7

 */
#define INFI 10000
double c[10][10];
double p[10];
int r[10][10];

void printC(int n)
{
	int i,j;
	for(i=1;i<=n+1;i++)
	{
		for(j=0;j<=n;j++)
		{
			if(i>j+1) printf("    ");
			else printf("%4.1f",c[i][j]);
		}
		cout<<endl;
	}
	cout<<endl;
}

void BST(int n)
{
	int i,j,d,k,minnum;
	double sum,min;
	for(i=1;i<=n;i++)
	{
		c[i][i-1]=0;
		c[i][i]=p[i];
		r[i][i]=i;
	}
	for(d=1;d<n;d++)
	{
		for(i=1;i<=n-d;i++)
		{
			j=i+d;
			sum=0;
			min=INFI;
			minnum=i;
			for(k=i;k<=j;k++)
			{
				sum+=p[k];
				if(min>c[i][k-1]+c[k+1][j])
				{
					min=c[i][k-1]+c[k+1][j];//动态规划函数
					minnum=k;
				}
			}
			c[i][j]=sum+min;
			r[i][j]=minnum;
			printC(n);
		}
	}
}

int main()
{
	int num,i;
	cin>>num;
	for(i=0;i<num;i++)
		cin>>p[i+1];
	BST(num);
	cout<<c[1][num]<<endl;
	return 0;
}