记录编号	602676	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2025-07-05 14:33:46	内存使用	3.73 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=35;
int n,d[N],ans=0,f[N][N],g[N][N];
void preorder(int l,int r)
{
    if(l>r) return;
    int x=g[l][r];
    cout<<x<<' ';
    preorder(l,x-1);
    preorder(x+1,r);
}
int main()
{
    freopen("jfecs.in","r",stdin);
    freopen("jfecs.out","w",stdout);
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>d[i];
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][i]=d[i],g[i][i]=i;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<=r;k++){
                int t;
                if(k==l) t=f[k+1][r]+d[k];
                else if(k==r) t=f[l][k-1]+d[k];
                else t=f[l][k-1]*f[k+1][r]+d[k];
                if(f[l][r]<t)
                {
                    f[l][r]=t;
                    g[l][r]=k;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    preorder(1,n);
    return 0;
}