记录编号	67964	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	zjh001	是否通过	通过
代码语言	C	运行时间	0.002 s
提交时间	2013-08-15 20:24:38	内存使用	0.37 MiB

#include <stdio.h>
#include <stdlib.h>
static unsigned int opt[100][100][2];
int a[101],n;

struct tree* build(struct tree* p,int x,int y);
void print(struct tree* p);

struct tree
{
	int data;
	struct tree* lch;
	struct tree* rch;
};

void init()
{
	struct tree* head;

	head=(struct tree*)malloc(sizeof(struct tree));
	head->data=opt[1][n][1];

	head=build(head,1,n);
	
	print(head);
}

void print(struct tree* p)
{
	if (p==NULL)
		return ;

	printf ("%d ",p->data);

	print(p->lch);

	print(p->rch);
}

struct tree* build(struct tree* p,int x,int y)
{
	if (x>y)
		return NULL;

	p->data=opt[x][y][1];

	p->lch=(struct tree*)malloc(sizeof(struct tree));
	p->rch=(struct tree*)malloc(sizeof(struct tree));

	p->lch=build(p->lch,x,p->data-1);
	p->rch=build(p->rch,p->data+1,y);
	return p;
}

void find()
{
	int i,j,z,max,t,t2;

	scanf ("%d",&n);
	for (i=1;i<=n;i++)
		scanf ("%d",&a[i]);

	for (i=1;i<=n;i++)
	{
		opt[i][i][0]=a[i];
		opt[i][i][1]=i;
	}

	for (i=1;i<n;i++)
	{
		for (j=1;j<=n-i;j++)
			{
				max=-1;

				for (z=j;z<=j+i;z++)	
				{
					if (z==j)
						t=opt[z+1][j+i][0]+a[z];
					else
						if (z==j+i)
							t=opt[j][z-1][0]+a[z];
						else
							t=opt[j][z-1][0]*opt[z+1][j+i][0]+a[z];

					if (t>max)
					{
						max=t;
						t2=z;
					}
				}
				opt[j][j+i][1]=t2;
				opt[j][j+i][0]=max;

		}
	}

	printf ("%d\n",opt[1][n][0]);
}



int main(){
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);

	find();

	init();


	return 0;
}
/*
5 
5 7 1 2 10
*/