noj 1007 加分二叉树 动态规划 树的遍列.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

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

//NOJ 1007 加分二叉树 动态规划 树的遍列
/*
输入：
5
5 7 1 2 10

输出：
145
3 1 2 4 5
*/
#define NMAX 32
long f[NMAX][NMAX];
int a[NMAX];
int root[NMAX][NMAX];
int xulie[NMAX];

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			printf("%3d",root[i][j]);
		cout<<endl;
	}
	cout<<endl;
//	system("pause");
}

void visit(int ll,int rr,int &count)
{	//得到先序遍列次序
	//访问从ll到rr的节点
	if(ll<rr&&ll>=0&&rr>=0)
	{
		xulie[count++]=root[ll][rr];//访问根节点
		visit(ll,root[ll][rr]-1,count);//访问左孩子
		visit(root[ll][rr]+1,rr,count);//访问右孩子
	}
	else if(ll==rr) 
		xulie[count++]=ll;//叶子节点
}

int cal(int num)
{
	int i,j,k,d,max,maxnum;
	for(i=1;i<=num;i++)
		for(j=1;j<=num;j++)
			f[i][j]=0;
	for(i=1;i<=num;i++)
		f[i][i]=a[i];
//	print(num);
	for(d=1;d<num;d++)
	{
		for(i=1;i<num;i++)
		{
			max=0;
			j=i+d;
			max=0;
			for(k=i;k<=j;k++)
			{	//以下转移方程就是根据题目意思写的-。-这话好白啊
				//注意两个边界情况
				if(k==i&&max<f[i][k]+f[k+1][j]) 
				{max=f[k][k]+f[k+1][j];maxnum=k;}
				else if(i<k&&k<j&&max<f[k][k]+f[i][k-1]*f[k+1][j])
				{max=f[k][k]+f[i][k-1]*f[k+1][j];maxnum=k;}
				else if(k==j&&max<f[i][k-1]+f[k][j])
				{max=f[i][k-1]+f[k][j];maxnum=k;}
			}
			f[i][j]=max;
			root[i][j]=maxnum;//记录根
//			print(num);
		}
	}
	
	return f[1][num];
}
int main()
{
	int i,num;
	int count=0;
	cin>>num;
	for(i=1;i<=num;i++)
		cin>>a[i];
	cout<<cal(num)<<endl;
	visit(1,num,count);
	for(i=0;i<num;i++)
		cout<<xulie[i]<<" ";
	cout<<endl;
	return 0;
}