蓝桥杯第十二届国赛D题：最小权值

对于一棵有根二叉树 T，小蓝定义这棵树中结点的权值 W(T) 如下：

空子树的权值为 0。如果一个结点 v 有左子树 L, 右子树 R，分别有 C(L) 和 C(R) 个结点，则：
W(v) = 1 + 2W(L) + 3W(R) + (C(L)) ^ 2 C(R)。树的权值定义为树的根结点的权值。小蓝想知道，对于一棵有 2021 个结点的二叉树，树的权值最小可能是多少？
 

解题思路：采用记忆化搜索来做。对于当前一共有x个节点，去掉根节点还有x-1。他的左节点可能有 0，1，2，3... x个。此时我们枚举他的左节点，它右节点的个数就等于x-左结点的个数-1

#include<bits/stdc++.h>
using namespace std;
const int maxn=2050;
const long long inf=1e18;
long long dp[maxn];
long long dfs(int now)
{
	if(dp[now]!=inf)return dp[now];
	for(int i=0;i<=now-1;i++)
	{
		dp[now]=min(dp[now],1+2*dfs(i)+3*dfs(now-i-1)+i*i*(now-i-1));
	}
	return dp[now];
}
int main()
{
    for(int i=1;i<=2021;i++)dp[i]=inf;
    long long ans=dfs(2021);
    cout<<ans<<endl;
    return 0;
}

最后结果：2653631372