g[l][r]存[l~r]中的根节点

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=40;
int a[N],n;
int f[N][N],g[N][N];
void dfs(int l,int r)
{
//  cout<<l<<" "<<r<<" "<<g[l][r]<<endl;
    if(l>r)return ;
    if(l==r)
    {
        printf("%d ",l);
        return ;
    }
    printf("%d ",g[l][r]);
    dfs(l,g[l][r]-1);

    dfs(g[l][r]+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i][i]=a[i];
    }
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l<=n;l++)
        {
            int r=l+len-1;
            if(r>n)break;
            for(int k=l;k<=r;k++)
            {
                int c=(max(1,f[l][k-1]))*(max(f[k+1][r],1))+a[k];
                if(f[l][r]<c)
                {
                    g[l][r]=k;
                    f[l][r]=c;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    dfs(1,n);

    return 0;
}