区间dp好题！
在更新 \(f[i][j]\) 时，顺便记录 该子树的根节点 \(g[i][j]\) 。
最后递归求解。
#include<bits/stdc++.h>
using namespace std;
class solve{
public:
int n;
int g[33][33];
int f[33][33];
void dfs(int l,int r)
{
if(l==r){
cout<<l<<" ";
return;
}
if(l>r)return;
cout<<g[l][r]<<" ";
dfs(l,g[l][r]-1);
dfs(g[l][r]+1,r);
}
void main()
{
cin>>n;
memset(f,0,sizeof(f));
for(int i=1; i<=n; i++)
cin>>f[i][i];
memset(g,0,sizeof(g));
for(int len=1; len<n; len++){
for(int i=1; i+len<=n; i++){
int j=i+len;
for(int k=i; k<=j; k++){
if(f[k][k]+(f[k+1][j]==0?1:f[k+1][j])*(f[i][k-1]==0?1:f[i][k-1])>f[i][j])
{
f[i][j]=f[k][k]+(f[k+1][j]==0?1:f[k+1][j])*(f[i][k-1]==0?1:f[i][k-1]);
g[i][j]=k;
}
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
}
}x;
int main()
{
x.main();
}