加分二叉树题解 记忆化搜索

加分二叉树

https://ac.nowcoder.com/acm/problem/16681

根据中序遍历特性,在根节点前面的节点,一定在左子树;根节点后面的节点,一定在右子树。我们可以根据这个特性,结合递归的方式确定出最高加分的二叉树。我们每次查询的过程中,
查询max(dp[l][i-1]*dp[i+1][r]+ans[i]);

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int ans[maxx];
int dp[35][35];
int root[35][35];
int pp=-0x3f3f3f;
void dfs(int l,int r)
{
    if(l>r)
    {
        dp[l][r]=1;
        return ;
    }
    if(l==r)
    {
        dp[l][r]=ans[l];
        root[l][r]=l;
        return ;
    }
    if(dp[l][r]==0)
    {
        for(int i=l;i<=r;i++)
        {
            dfs(l,i-1);
            dfs(i+1,r);
            int tem=dp[l][i-1]*dp[i+1][r]+ans[i];
            if(tem>dp[l][r])
            {
                dp[l][r]=tem;
                root[l][r]=i;
            }
            pp=max(pp,dp[l][r]);
        }
    }
}
void print(int l,int r)
{
    if(l>r) return ;
    cout<<root[l][r]<<" ";
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
   fio;
   int n;
   cin>>n;
   for(int i=1;i<=n;i++)
    cin>>ans[i];
   dfs(1,n);
   cout<<pp<<endl;
   print(1,n);
    return 0;
}
全部评论

相关推荐

白火同学:只是实习的话,你这份简历应该也差不多了。真要优化的话,因为面实习的话,没有开发经验,面试更重视技术栈水平。 1、重视JavaSE的基础吧,集合、泛型算是比较基础的基础,多线程、反射、JVM内存模型才是基础; 2、技术栈写到具体的点,比如Elasticsearch的使用写到某个点,限制面试官自由发挥,防止问了相关问题最后又答不上,如果真没把握建议不写,降低面试官的心理预期; 3、技术栈不要重复,比如技术栈第二条和第八条可以合并改为“熟悉Redis中间件,包括基本数据结构、缓存策略、持久化机制,了解缓存三剑客及其解决方案,并有相关项目经验。”; 4、项目指标量化,比如“达到xx秒的响应速度”(不过这个就有点偏校招社招的要求了,实习简历不写也无伤大雅)。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:45
你不要过来啊啊啊啊啊啊啊
码农索隆:对面:“今天你不面也得面”
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务