洛谷P1040 加分二叉树题解

dp即可

\(f[i][j]\)表示i到j的加分

相当于区间dp了

#include<cstdio>

using namespace std;

int v[50];

int f[55][55];

int root[55][55];

void print(int l,int r)

{

	if(l>r)return ;

	if(l==r)

	{

		printf("%d ",r);

		return ;

	}

	int tmp=root[l][r];

	printf("%d ",tmp);

	print(l,tmp-1);

	print(tmp+1,r);

}

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&v[i]);

		f[i][i]=v[i];

		f[i][i-1]=1;

	}

	for(int i=n-1;i>=1;i--)

	{

		for(int j=i+1;j<=n;j++)

		{

			for(int k=i;k<=j;k++)

			{

				if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k]))//k为根节点

				{

					f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];

					root[i][j]=k;

				}

			}

		}

	}

	printf("%d\n",f[1][n]);

	print(1,n);//输出中序遍历

	return 0;

}

巴特西

洛谷P1040 加分二叉树题解

dp即可

最新文章

热门文章