草庐IT

luogu_P1040 [NOIP2003 提高组] 加分二叉树

leexiao 2024-01-15 原文

P1040 [NOIP2003 提高组] 加分二叉树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：给你一颗中序遍历为1到n的二叉树，和每个节点的val。树的值=左子树的值×右子树的值+根的val，空树值为1，求整个树最大值和这个值树的前序遍历。

题解：区间dp。dp[l][r]表示最大值，root[l][r]表示最大值的根，枚举区间然后枚举根，根据题目中的计算公式搞最大值。

　　树形dp。一样的dp[l][r]表示子树罢了。

　　多想想，一步步讨论就好了，关键是找能做出答案的状态表示再想转移方程。

int n,a[N],dp[N][N],rt[N][N];
void pre_ans(int l,int r){
    if(l>r) return;
    cout<<rt[l][r]<<" ";
    pre_ans(l,rt[l][r]-1);
    pre_ans(rt[l][r]+1,r);
}
void solve(){
    cin>>n;
    rep(i,1,n+1) cin>>a[i],dp[i][i]=a[i],rt[i][i]=i;
    for(int len=1;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r = l+len-1;
            dp[l][r] = dp[l + 1][r] + dp[l][l];//左子树为空
            rt[l][r]=l;
            for(int k=l+1;k<r;k++){//左子树的节点数  枚举子树的根
                if(dp[l][r]<dp[l][k-1]*dp[k+1][r]+dp[k][k]){
                    dp[l][r]=dp[l][k-1]*dp[k+1][r]+dp[k][k];
                    rt[l][r]=k;
                }
            }
            if(dp[l][r]<dp[l][r-1]+dp[r][r]){
                dp[l][r]=dp[l][r-1]+dp[r][r];
                rt[l][r]=r;
            }
        }
    }
//    for(int len=1;len<=n;len++){
//        printf("len=%d\n",len);
//        for(int l=1;l+len-1<=n;l++){
//            int r = l+len-1;
//            printf("dp[%d][%d]=%d ",l ,r ,dp[l][r]);
//        }
//        printf("\n");
//    }
    cout<<dp[1][n]<<"\n";
    pre_ans(1,n);
}
luogu_Pluoguspanclasscpp0C++

有关luogu_P1040 [NOIP2003 提高组] 加分二叉树的更多相关文章

  1. 程序员如何提高代码能力？ - 2

    前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源

  2. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  3. ruby - 用于提高 Ruby 技能的紧凑型 gem 或库？ - 2

    我是高级初学者/中级Ruby程序员。我真的在努力提高我的Ruby技能，特别专注于编写更高效、紧凑、惯用的Ruby，遵循可靠的测试实践，学习并遵守项目结构和其他一般最佳实践。考虑到这一点，我一直在寻找好的Material来学习。我已经检查了几个PlayByPlayPeepcodescreencasts，这很棒，但不完全是我想要的。我浏览了Github，但我熟悉的大多数项目都非常庞大——我花了太多时间来解开事物实际上是如何组合在一起的，并试图建立事物的心智模型，而不是我真正花时间去理解开发过程。因此，我正在寻找紧凑、构建良好等优质项目/gems/libs的好例子。我更喜欢自包含的东西，即不

  4. ruby - Rspec 不工作，或提高不提高？ - 2

    我正在一边学习TDD，一边编写一些小的ruby​​程序。我有以下类(class):classMyDirectorydefcheck(dir_name)unlessFile.directory?(dir_name)thenraiseRuntimeError,"#{dir_name}isnotadirectory"endendend我正在尝试用这个rspec测试来测试它。describeMyDirectorydoit"shoulderrorifdoesn'texist"doone=MyDirectory.newone.check("donee").shouldraise_exception

  5. javascript - 提高长轮询 Ajax 性能 - 2

    我正在编写一个网络应用程序(仅与Firefox兼容)，它使用长轮询(通过jQuery的ajax功能)从服务器向客户端发送或多或少的持续更新。我担心长时间运行(例如，整天或整夜)的影响。基本的代码框架是这样的:functionprocessResults(xml){//dostuffwiththexmlfromtheserver}functionfetch(){setTimeout(function(){$.ajax({type:'GET',url:'foo/bar/baz',dataType:'xml',success:function(xml){processResults(xml)

  6. javascript - 提高 Chrome JS 堆限制？ - 2

    我有一个使用太多内存的JavaScript应用程序。它不会使选项卡崩溃，但加载可能需要几分钟，其中大部分时间都花在了GC上。我正在使用堆分析器查看哪些函数分配的内存最多，效果很好。有没有什么方法可以让Chrome允许每个进程使用更大的JS堆，这样我就可以在减少内存压力的情况下进行测试运行，而无需等待GC几分钟？也许是我找不到的命令行参数？ 最佳答案 是的，控制台中报告了jsHeapSizeLimit:>console.memoryMemoryInfo{totalJSHeapSize:42100000,usedJSHeapSize:2

  7. javascript - 如何提高 IE8 对大数据集的性能？ - 2

    我有一个页面显示了大约300页的表格数据。Firefox、Chrome、Safari都可以正常工作，但IE7、8和8的兼容性View都很糟糕。当我尝试滚动或按下向上翻页/向下翻页按钮时，它会滞后几秒钟。分页、较小的数据集和其他可用性建议不适用于此页面。假设我别无选择，只能一次显示所有这些数据……我可以做些什么来调整它？数据是通过jQuery/Ajax加载的，这似乎至少在某种程度上是可疑的，因为当我创建一个测试页面来直接呈现结果时，它并不相当那么慢，但仍然不如其他浏览器那么活泼。我过去曾成功使用SlickGrid等jQuery插件来解决类似问题，但由于需要很长时间才能解释的原因，即使使用

  8. jquery - 停止事件冒泡 - 提高性能？ - 2

    如果我不回来了false来自事件回调，或使用e.stopPropagationjQuery的特性，事件使DOM冒泡。在大多数情况下，我不关心事件是否冒泡。就像这个DOM结构示例一样:​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​通常，我没有像这样的多个嵌套提交回调:$('#theDiv').submit(function(){alert('DIV!');});$('#theForm').submit(function(e){alert('FORM!'

  9. javascript - 通过采样/插值减少大型数据集的大小以提高图表性能 - 2

    我有一大组(>2000)时间序列数据，我想在浏览器中使用d3显示这些数据。D3非常适合向用户显示数据的一个子集(~100点)，但我还想要一个“上下文”View(likethis)来显示整个数据集并允许用户选择作为子区域进行查看细节。但是，当尝试在d3中显示那么多点时，性能很糟糕。我觉得一个好的解决方案是选择一个数据样本，然后使用某种插值(样条、多项式等，这是我知道怎么做的部分)来绘制一条与实际数据。但是，我不清楚应该如何选择子集。数据(如下所示)具有相当平坦的区域，在这些区域需要较少的样本才能进行适当的插值，而其他区域的绝对导数非常高，需要更频繁的采样。更复杂的是，数据存在间隙(生成数

  10. javascript - jQuery - 提高性能/代码 - 2

    我刚开始使用jQuery，并且一直在寻找有关如何提高代码速度/性能的某种类型的资源。我想知道是否有人有任何提示或资源可以帮助我。谢谢，贝弗 最佳答案 我在这个主题上收藏了一些网站，希望它们能帮助您解决您需要的问题。(主题范围从简单到高级)jQueryPerformanceRules主题包括:AlwaysDescendFroman#idUseTagsBeforeClassesCachejQueryObjectsHarnessthePowerofChainingUseSub-queriesLimitDirectDOMManipulati

随机推荐