前言:

树的遍历,以前学的时候就很懵逼...

今天就来记录下树的四种遍历.

思路:

这题思路比较简单.区间dp一下即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=32;
ll w[N];
ll f[N][N];//这个区间的最优答案是多少.
int root[N][N];//这一段的根是多少.
ll solve(int l,int r)
{
    if(f[l][r])    return f[l][r];
    if(l==r)       return f[l][r]=w[l];
    if(l>r)        return 1ll;
    for(int i=l;i<=r;i++)
    {
        ll res=solve(l,i-1)*solve(i+1,r)+w[i];
        if(res>f[l][r])    f[l][r]=res,root[l][r]=i;
    }return f[l][r];
}

void print(int l,int r)
{
    if(l==r)    {printf("%d ",l);return;}
    if(l>r)     return;
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}

int main()
{
    ll n;cin>>n;
    for(int i=1;i<=n;i++)    cin>>w[i];
    printf("%lld\n",solve(1,n));
    print(1,n);puts("");
    return 0;
}