1. 题目

传送门＝￣ω￣＝

2. 题解

你可以把这题看成树型 dp。
但其实这应该算是个。。。区间 dp。
给出的序列是中序遍历。。。
中序遍历是按 “左-根-右” 方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边。。。
所以我们设 $f[i,j]$为中序遍历为 $i,i+1,i+2,i+3,…,j$的树的最大分数。
则:$f[i,j]=max{f[i,k-1]×f[k+1,j] +d[k]|1<=i<=k=<=j<=n}$
其中 $d[i]$表示节点 $i$的值，$f[i,i]=d[i]$

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,v[35],f[35][35],rt[35][35];
LL dfs(LL l,LL r)
{
    if(f[l][r]!=-1)return f[l][r];
    if(l==r)return rt[l][r]=l,f[l][r]=v[l];
    LL k;
    if(k=dfs(l+1,r)+v[l],k>f[l][r])f[l][r]=k,rt[l][r]=l;
    for(LL i=l+1;i<r;i++)
    {
        k=dfs(l,i-1)*dfs(i+1,r)+v[i];
        if(k>f[l][r])f[l][r]=k,rt[l][r]=i;
    }
    if(k=dfs(l,r-1)+v[r],k>f[l][r])f[l][r]=k,rt[l][r]=r;
    return f[l][r];
}
void pans(LL l,LL r)
{
    if(l>r)return;
    printf("%lld ",rt[l][r]),pans(l,rt[l][r]-1),pans(rt[l][r]+1,r);
}
int main()
{
    memset(f,-1,sizeof(f)),scanf("%lld",&n);
    for(LL i=1;i<=n;i++)scanf("%lld",&v[i]);
    printf("%lld\n",dfs(1,n)),pans(1,n);
    return 0;
}