第十二届蓝桥杯国赛C++ B组 最小权值

题目

小记

在赛场紧张刺激的氛围中突然遭遇一道填空题压轴题让我措手不及。起初我以为一棵树必须是完美二叉树，并通过数组模拟完美二叉树的过程自诩为一种高超的技术能力。然而快到题目完成时分 realize 树不一定非要完美二叉形——意识到这种假设可能过于理想化——于是决定转而寻找其他得分途径变得明智起来

解题思路

对于补题者而言，在重新审视这道题目时会发现其实并不困难。该问题属于典型的基于自顶向下的动态规划求解方式。采用自顶向下的策略，在确保每个阶段都达到局部最优的前提下，则整体问题的全局最优自然得以实现。

代码

运行结果：2653631372

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll dp[2022];
    int main()
    {
    memset(dp,0x7f,sizeof(dp));//初始化最大值；
    dp[0]=0;//根据题意，当子树为空时权值为0；