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

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);
}

原文链接：https://www.cnblogs.com/leexiao/p/17358940.html