题解 | #[NOIP2003]加分二叉树#

#include<iostream>
using namespace std;
int n;
int p=0;
int tree[40];
int dp[40][40];
int root[40][40];
int a[40];
void built(int l ,int r)
{
    int at=l;
    dp[l][l]=a[l],dp[r][r]=a[r];
    if(l!=r) 
        for(int i=l;i<=r;i++) dp[l][r]+=a[i];
    for(int k=l;k<=r;k++)
    {
        int ll=dp[l][k-1],rr=dp[k+1][r];
       if(!dp[l][k]) ll=1;
        if(!dp[k][r]) rr=1;
       if(ll*rr+a[k]>dp[l][r])
       {
           dp[l][r]=ll*rr+a[k];
           at=k;
        }
      
    }
    root[l][r]=at;
    
    return ;
}
void find(int l,int r)
{
//     cout<<l<<" "<<r<<endl;
    if(l==r) 
    {
        tree[p]=l;
        return ;
    }
   
    int at=root[l][r];
    tree[p]=at;
    if(at-1>=l)
    {
        
    p++;
    find(l,at-1);
    }
    if(at+1<=r)
    {
        
    p++;
    find(at+1,r);
        }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j>=1;j--)
        {
            built(j,i);
//             cout<<j<<" "<<i<<" "<<dp[j][i]<<" "<<root[j][i]<<endl;
        }
//         cout<<"----"<<endl;
    }
//     for(int i=1;i<=n;i++)
//     {
//         for(int j=1;j<=i;j++)
//             cout<<dp[i][j]<<" ";
//         cout<<endl;
//     }

            
    cout<<dp[1][n]<<endl;
    find(1,n);
    for(int i=0;i<n;i++) cout<<tree[i]<<" ";
}