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

加分二叉树

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;
}
全部评论

相关推荐

认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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