2021第十二届蓝桥杯国赛-D最小权值

2021-08-04 · 70次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #动态规划

题面

【问题描述】

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

空子树的权值为 0。

如果一个结点 v 有左子树 L, 右子树 R，分别有 $C(L)$ 和 $C(R)$ 个结点，则

$W(v) = 1 + 2W(L) + 3W(R) + (C(L))^2C(R)$

树的权值定义为树的根结点的权值。

小蓝想知道，对于一棵有 2021 个结点的二叉树，树的权值最小可能是多少？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路

动态规划

考虑子问题，从一个节点一直增到2021个节点的情况，记 $f[i]$ 表示节点数为 $i$ 的二叉树的最小权值，则其状态转移方程为：

$f[i] = \min_{0 < j < i - 1}\{1 + 2 * f[j] + 3 * f[i - j - 1] + j^2 * (i - j - 1)\}$

其中， $j$ 表示根节点的左子树的节点数目，则右子树的节点数目为 $i - j - 1$ 。

答案：2653631372

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
LL f[2100];
int n = 2021;

int main() {
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            f[i] = min(f[i], 1 + 2 * f[j] + 3 * f[i - j - 1] + j * 1ll * j * (i - j - 1));
        }
    }
    cout << f[n] << endl;

    return 0;
}

标题：	2021第十二届蓝桥杯国赛-D最小权值
链接：	https://www.fightingok.cn/detail/125
更新：	2022-09-18 22:41:03
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可

2021第十二届蓝桥杯国赛-D最小权值

题面

【问题描述】

【答案提交】

思路

代码

Cyan