主题表示小信号群中有由n个节点组成的二叉树，每个节点都有权重。 将二叉树各边的开销定义为其两端节点权重的乘积，作为二叉树的总开销，即各边开销之和。 小信号群通过二叉树的中顺扫描依次记录各节点的权重。 也就是说，他记录了n个个数，第I个个数表示中顺扫描的第I个位置上的节点的权重。 后来，由于某种原因，小组忘记了二叉树的具体结构。 在可能的二叉树中，总成本最小的二叉树被称为最优二叉树。 现在，小组请求最适合sqdwk的二叉树总支出。
输入说明：的第一行，然后输入表示二叉树节点数的整数n(1=n=300 )。
在第二行中，输入以空格分隔的n个整数。 这意味着按中顺序遍历记录中每个节点的权重，所有权值为小于或等于1000的正整数。
输出描述：输出指示最佳二叉树总开销的整数。
输入示例1: 5
7 6 5 1 3
输出示例1: 45
题解
记忆化搜索
列举各a[i]是现在的根节点，检索a[i]的左边是左边的子节点，a[i]的右边是右边的子节点，计算最大值
# include bits/stdc.husingnamespacestd； const int N=300 10； int a[N]； int d[N][N][N]； intDFS(intL，int r，int p ) if ) LR ) return 0； if(d(l ) [r][p]！=-1 ) return d[l][r][p]； int res=1e9； for(intI=L； i=r； I ) intleft=DFS(L，i-1，I )； intright=DFS(I1，r，I )； RES=min(RES，left right a[p]*a[i]； } d[l][r][p]=res； return d[l][r][p]； (}int main ) ) { int n； cin n； memset(d，-1，sizeof d )； for(intI=1； i=n； I () { cin a[i]； }coutDFS(1，n，0 ) endl； 返回0； }