ACM资料大集合

				#include 
				#include 
				#include 
				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					{
						for(j=0;j						{
							if(i>j+1) printf("    ");
							else printf("%4.1f",c[i][j]);
						}
						cout					}
					cout				}
				
				void BST(int n)
				{
					int i,j,d,k,minnum;
					double sum,min;
					for(i=1;i					{
						c[i][i-1]=0;
						c[i][i]=p[i];
						r[i][i]=i;
					}
					for(d=1;d					{
						for(i=1;i						{
							j=i+d;
							sum=0;
							min=INFI;
							minnum=i;
							for(k=i;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						cin>>p[i+1];
					BST(num);
					cout					return 0;
				}