（2021年第十二届蓝桥杯国赛）D：最小权值（动态规划）

十二届蓝桥杯国赛）D：最小权值（动态规划）"/>

（2021年第十二届蓝桥杯国赛）D：最小权值（动态规划）

分析：这道题目是用动态规划来解决的，而且比较容易想到状态表示方法：f[i]代表有i个节点的树的最小权值，我们下面来分析一下怎样进行状态转移方程的推导

对于有i个节点的树而言，这棵树的权值取决于根节点的左右子树的分布，我们能够枚举的只是左右子树的节点个数分布，无法直接枚举左右子树形态分布，再看一下题目中所给的权值计算方法可以得到一个结论，树的权值是随着左右子树的权值变小而变小的，也就是说在其他条件不变的情况下（这里的其他条件指的是另一棵子树的形态不变以及节点个数不变），改变某一棵子树的形态使其权值变小则会使整棵树的权值变小，由于左右子树的形态是相互独立的，也就是说在左右子树节点个数一定的情况下我们只需要使得左右子树的权值分别达到最小即可，而这正是我们状态表示中所涵盖的信息，因此就有了状态转移的方程:

f[i]=min(1+2*f[j]+3*f[i-1-j]+j*j*(i-1-j),f[i])

j是当前根节点左子树的节点个数，而i是当前子树中所有节点的个数，所以右子树的节点个数就是i-j-1(1是根节点)，f[j]和f[i-j-1]分别表示在左右子树节点个数一定的情况下的最小权值，这是由于函数的性质决定的，所以我们只需要遍历左右子树的节点个数求一个最小值即可。

由于求的是最小值，所以一开始不要忘记把所有的f数组初始化为正无穷大，把f[0]初始化为0.

下面是代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=3003;
long long f[N];//f[i]表示一棵节点个数为n的子树的最小权值 
int main()
{memset(f,0x3f,sizeof f);f[0]=0;for(int i=1;i<=2021;i++)for(int j=0;j<=i-1;j++)//枚举左子树节点个数f[i]=min(1+2*f[j]+3*f[i-1-j]+j*j*(i-1-j),f[i]);cout<<f[2021];return 0; 
}