思路

区间DP（类似于）

一开始我设计的状态是f[L][R][rot]表示在中序遍历的区间[L, R]中选取rot为根节点，得到的最大加分。

后来翻看题解发现，状态中的rot项并不重要，对于第一问，我们只关心$[L, R]$区间中构建成一棵树后得到的最大加分值，不关心这棵树的形态。

于是设计状态为f[L][R]在区间[L, R]为中序遍历时，形成的最大加分值。

转移过程中枚举区间$[L, R]$中的一个点作为根节点，计算加分，更新$f[i][j]$。

对于输出先序遍历，我们需要知道每一段$[L, R]$中的根结点时那个才能构造出先序遍历，简单说就是需要知道树的形态。可以在转移的过程中进行记录，例如$root[L][R]$表示在中序遍历的区间中$[L, R]$的根节点。

/*!
 * FileName: luogu-1040.cpp
 * This Problem is on luogu. The ID of the problem is 1040. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-10-27 08:43:19 written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define _R register 
#define inf 0x7fffffff
using namespace std;
const int _ = 110;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int n;
int A[_]; 
int f[_][_];
int root[_][_];
void printTree(int L, int R){
    if(L == R){
        printf("%d ", L);
        return ;
    }
    if(L > R) return ;
    int rt = root[L][R];
    printf("%d ", rt);
    printTree(L, rt - 1);
    printTree(rt + 1, R);
}
int main()
{
    n = read();
    for(_R int i = 1;i <= n;i++) A[i] = read();
    for(_R int i = 0;i <= n;i++){
        for(_R int j = 0;j < i;j++)
            f[i][j] = 1;
    }
    for(_R int i = 1;i <= n;i++)f[i][i] = A[i], root[i][i] = i;
    for(_R int len = 2;len <= n;len++){
        for(_R int L = 1;L + len - 1 <= n;L++){
            int R = L + len - 1;
            for(_R int k = L;k <= R;k++){
                if(f[L][R] < f[L][k - 1] * f[k + 1][R] + A[k]){
                    f[L][R] = f[L][k - 1] * f[k + 1][R] + A[k];
                    root[L][R] = k; 
                }
            }
        }
    }
    printf("%d\n", f[1][n]);
    printTree(1, n);
    return 0;
}