思路：从1到n让每个点为根节点，然后计算出左子树分数最大值，右子树分数最大值，最后计算整棵树的最大值。
#include#include #include using namespace std; int n; int w[30]; int f[30][30],g[30][30]; void dfs(int l,int r) { if(l>r) return ; int root=g[l][r]; printf("%d ",root); dfs(l,root-1); dfs(root+1,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int len=1;len<=n;len++)//长度 for(int l=1;l<=n-len+1;l++)//起点 { int r=l+len-1;//终点 if(len==1)//当长度为1，该点没有左子树和右子树，该点为根节点 { f[l][r]=w[l]; g[l][r]=l; } else { for(int k=l;k<=r;k++) { int ll,rr; if(k==l)//没有左子树 ll=1; else ll=f[l][k-1]; if(k==rr)//没有右子树 rr=1; else rr=f[k+1][r]; int s=ll*rr+w[k]; if(f[l][r]
