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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[32],dp[32][32],id;
vector<int> v[32][32];
int main(){
    freopen("jfecs.in","r",stdin);
    freopen("jfecs.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i][i]=a[i];
        v[i][i].push_back(i);
    }
    for(int i=2;i<=n;i++)
    for(int l=1;l<=n-i+1;l++){
        int r=l+i-1;
        if(l!=r){
            for(int k=l;k<=r;k++)
            if(max(dp[l][k-1],1)*max(dp[k+1][r],1)+a[k]>dp[l][r]){
                dp[l][r]=max(dp[l][k-1],1)*max(dp[k+1][r],1)+a[k];
                id=k;
            }
            v[l][r].push_back(id);
            for(int j=0;j<v[l][id-1].size();j++) v[l][r].push_back(v[l][id-1][j]);
            for(int j=0;j<v[id+1][r].size();j++) v[l][r].push_back(v[id+1][r][j]);
        }
    }
    cout<<dp[1][n]<<endl;
    for(int i=0;i<v[1][n].size();i++) cout<<v[1][n][i]<<' ';
}