蓝桥杯官网填空题(最小权值)

发布时间:2024年01月24日

题目描述

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

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

空子树的权值为 0 。

如果一个结点? v?有左子树? L, 右子树? R,分别有? C(L)?和? C(R)?个结点,则? W(v)=1+2W(L)+3W(R)+(C(L))^2*C(R)

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

小蓝想知道,对于一棵有?

2021?个结点的二叉树,树的权值最小可能是多少?

运行限制

//动态规划

import java.util.*;

public class Main {
    public static void main(String[] args) {
	  long[] dp=new long[2022];
      Arrays.fill(dp,Long.MAX_VALUE);
      dp[0]=0;
      for(int i=1;i<=2021;i++){
        for(int L=0;L<i;L++){
          int R=i-L-1;
          dp[i]=Math.min(dp[i],1+2*dp[L]+3*dp[R]+(long)Math.pow(L,2)*R);
        }
      }
      System.out.println(dp[2021]);
	}
}

    • 最大运行时间:1s
    • 最大运行内存: 128M
文章来源:https://blog.csdn.net/s44Sc21/article/details/135779568
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。