#10158. 「一本通 5.2 练习 1」加分二叉树（区间dp+递归输出路径）-爱代码爱编程

libreoj10158

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=105;
int n;
LL b[maxn],dp[maxn][maxn];
int root[maxn][maxn];
vector<int> v;
void dfs(int l,int r)
{
    if(l>r)return ;
    v.push_back(root[l][r]);
    dfs(l,root[l][r]-1);
    dfs(root[l][r]+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    memset(dp,0LL,sizeof(dp));
    for(int i=1;i<=n;i++){
        dp[i][i]=b[i];
        root[i][i]=i;
    }
    for(int i=2;i<=n;i++){
        for(int l=1;l<=n-i+1;l++){
            int r=l+i-1;
            for(int k=l;k<=r;k++){
                 LL lsum=1;
                 if(k-1>=l){
                    lsum*=dp[l][k-1];
                 }
                 LL rsum=1;
                 if(k+1<=r){
                    rsum*=dp[k+1][r];
                 }
                 if(dp[l][r]<(lsum*rsum+b[k])){
                    dp[l][r]=(lsum*rsum)+b[k];
                    //pre[l][r]=k;
                    root[l][r]=k;
                 }
            }
        }
    }
    printf("%lld\n",dp[1][n]);
    v.clear();
    dfs(1,n);
    for(int i=0;i<v.size();i++){
        printf("%d ",v[i]);
    }
    printf("\n");
    return 0;
}