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

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,a[35],f[35][35],rt[35][35];

void dfsout(ll l,ll r){
    if(l>r)return;
    cout<<rt[l][r]<<endl;
    dfsout(l,rt[l][r]-1);
    dfsout(rt[l][r]+1,r);
}

int main(){
    cin>>n;
    foru(i,1,n){
        cin>>a[i];
        f[i][i]=a[i];
        f[i][i-1]=1;
        rt[i][i]=i;
    }
    foru(l,1,n-1){
        foru(i,1,n-l){
            ll j=i+l;
            f[i][j]=f[i][i]+f[i+1][j];
            rt[i][j]=i;
            foru(k,i+1,j-1){
                if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k]){
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    rt[i][j]=k;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    dfsout(1,n);
    return 0;
}