[数据结构与算法] P1040 [NOIP2003 提高组] 加分二叉树

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> P1040 [NOIP2003 提高组] 加分二叉树 -> 正文阅读

[数据结构与算法]P1040 [NOIP2003 提高组] 加分二叉树

//树状动态规划

//P1040 [NOIP2003 提高组] 加分二叉树

//f[i][j]=MAX(f[i][k?1]?f[k+1][j]+f[k][k])

const int maxn =50;

#define  ll long long

ll n;
ll result[maxn][maxn],root[maxn][maxn];


void print(int l,int r)//输出l到r区间的根节点
{
    if(l>r) return;
    printf("%lld ",root[l][r]);
    if(l==r) return;//到达也节点就结束
    //前序遍历
    print(l,root[l][r]-1);//打印左子树的根节点
    print(root[l][r]+1,r);//打印右子树的根节点
}



int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&result[i][i]);
        result[i][i-1]=1;//空子树规定为1
        root[i][i]=i;//每个节点的根节点就是他们自己
    }

    for(int len=2;len<=n;len++)//区间长度为2到len 区间长度为1就是result[i][i]
    {
        for(int i=1;i+len-1<=n;i++)//左端点，右端点为i+len-1，最大为n保证不越界
        {
            int j=i+len-1;
            result[i][j]=result[i][i]+result[i+1][j];

            //开始选根节点，看区间内哪个点作为根节点的时候，得到的值最大

            root[i][j]=i;//默认从i到j区间的根节点为左端点i

            for(int k=i;k<j;k++)//采用左闭右开区间
            {
                if(result[i][j]<result[i][k-1]*result[k+1][j]+result[k][k])
                {
                    result[i][j]=result[i][k-1]*result[k+1][j]+result[k][k];
                    root[i][j]=k;//更新根节点
                }
            }
        }
    }
    cout << result[1][n] << endl;//打印输出1到n区间的最大加分值
    print(1,n);//打印先从1到n区间的根节点开始
    return 0;
}