# 思路
区间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]$的根节点。
```cpp
/*!
* 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;
}
```