二叉树？？树状dp？？NONONO！！！
本题的树不固定，他要求去找出来一个最优的树，所以不适合使用树状dp去进行求解。但又因为题中所给的有中序遍历的序列，中序遍历序列最大的特点在于定根可将区间分成左右子树。
那么分成两部分之后就可以分别去计算这两部分，也就是在这两小部分里面取找根。
那么可以得到dp[i][j]为i,j这个区间组成的树的最高加分。
得到状态转移方程为：dp[i][j] = max(dp[i][k], dp[k+1][j])。
对于前序遍历：在每一个区间树遍历最高加分的时候去记录最优的那个根。然后重新dfs遍历得到就行。
//题目中所给的是一个中序遍历的序列，那么只要定下一个根就可以将这个序列分成左右两部分。
//分成两部分之后就可以分别去计算这两部分，也就是在这两小部分里面取找根。
//那么可以得到dp[i][j]为i,j这个区间组成的树的最高加分。
//得到状态转移方程为：dp[i][j] = max(dp[i][k], dp[k+1][j])。
//对于前序遍历：在每一个区间树遍历最高加分的时候去记录最优的那个根。然后重新dfs遍历得到就行。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 33;
int n;
int a[maxn];
int dp[maxn][maxn];
int zhong[maxn][maxn];

void dfs(int l, int r)
{
    if (l==r)
    {
        cout<<l<<' ';
        return ;
    }
    if (l>r) return ;
    int mid = zhong[l][r];
    int l1 = l;
    int r1 = mid-1;
    int l2 = mid+1;
    int r2 = r;
    cout<<mid<<" ";
    dfs(l1, r1);dfs(l2, r2);
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int len = 1;len<=n;len++)
    {
        for (int l = 1;l<=n-len+1;l++)
        {
            int r = l+len-1;
            if (len==1) 
                dp[l][r] = a[l];
            else{
                for (int k=l;k<=r;k++)
                {
                    int num = (l<=k-1? dp[l][k-1]:1) * (k+1<=r? dp[k+1][r]:1) + dp[k][k];
                    if (dp[l][r]<num)
                    {
                        dp[l][r] = num;
                        zhong[l][r] = k;
                    }
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;
    //通过之前记录的来进行dfs输出前序遍历
    dfs(1, n);
    return 0;
}