蓝桥杯备战日志(Python)22-最小权值&本质上升序列-(二叉树的形式、动态规划)

最小权值

原题

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

空子树的权值为 0。

如果一个结点 v 有左子树 L, 右子树 R，分别有 C(L) 和 C(R) 个结点，则 W(v) = 1 + 2W(L) + 3W(R) + (C(L))² C(R)。树的权值定义为树的根结点的权值。

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

分析

本题在考查二叉树的形式的同时结合动态规划的知识，根据题意，我们需要知道n=2021个结点的二叉树的”权值”最小值W(n)，而W(n)的值又有该二叉树的左右子树的”权值“（应该说两棵子树的结点数量）决定，此时有两种极端的形式：只有右子树或者只有左子树（都是n-1个结点），所有这里可以从一种”极端“形式走到另一种”极端“形式，实现细节如下：

• 对于一棵有node_num个结点的二叉树，设其左右子树的结点个数分别为left, right，该二叉树形式可以有左右结点的不同数量表示

• 只有右子树时，left=0, right=nude_num-1
• 只有左子树时，left=nude_num-1, right=0
• 除以上两种情况，还有左右子树都存在的其它形式

• 根据以上左右子树结点数的情况，更新当前有node_num个结点的二叉树的“权值”的最小值
• node_num的取值为区间[1, n]

具体实现结合以下“源码”部分理解。

源码

n = 2021
# 数组Wn的元素Wn[i]存放有i个结点的树的“最小权值”，初始为0
Wn = [0] * (n+1)

for node_num in range(1,n+1):
    Wn[node_num] = 1e10  # 10000000000.0
    # 对于结点数量为node_num的二叉树，计算得到其最小权值
    # 从该树只有右子树的情况开始“找”，然后右子树的结点一个一个地“移”到左子树，直到二叉树的另一种“极端”形式——只有左子树
    left = 0
    right = node_num-1
    while left  node_num:
        t = 1 + 2 * Wn[left] + 3 * Wn[right] + left*left*right
        if t  Wn[node_num]:
            Wn[node_num] = t
        # 左子树结点+1，右子树结点-1
        left += 1
        right -= 1

print(Wn[n])  # 输出：2653631372

本质上升序列

原题

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 ​​lanqiao​​​ 中，如果取出字符 ​​n​​​ 和 ​​q​​​，则 ​​nq​​​ 组成一个单调递增子序列。类似的单调递增子序列还有 ​​lnq、i、ano​​​ 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ​​ao​​​，取最后两个字符也可以取到 ​​ao​​。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 ​​l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio​​。

请问对于以下字符串（共 

 个小写英文字母，分四行显示）：

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

分析

这里考查“动态规划”的应用，根据题意，可由如下算法计算得到所有本质上升序列的数量。

• 数组str_alp顺序存储每个字母
• 数组res_l中的元素res_l[i]存放以字母str_alp[i]为结尾的“本质上升序列”的数量，初始值为1（即序列只含字母本身的情况）
• 按顺序遍历str_alp中的每个字母，当访问到字母str_alp[i]时，我们可以在区间[i+1,n)内遍历所有在str_alp[i]的字母str_alp[j]

• 当 str_alp[j] > str_alp[i] 时，此时res_l[j]值需要加上res_l[i]的值
• ​当 str_alp[j] == str_alp[i] 时，说明前面重复统计了以字母str_alp[i]为结尾的“本质上升序列”的数量，所有此时res_l[j]值需要减去res_l[i]的值

• 最后数组res_l所有元素的和即为最终所求

源码

str_alp = 'tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl'

n = len(str_alp)
# 初始以str_alp[i]结尾的每个上升序列的数目为1
res_l = [1] * n

# 在以str_alp[i]结尾的序列的基础上，尝试在末尾添加“以str_alp[j]结尾的序列”
for i in range(n):
    for j in range(i+1,n):
        if str_alp[j] > str_alp[i]:
            res_l[j] += res_l[i]
        elif str_alp[j] == str_alp[i]:
            res_l[j] -= res_l[i]
print(sum(res_l))

上一篇：​​蓝桥杯备战日志(Python)21-排列小球-(递归搜索)​​

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net