AcWing 479. 加分二叉树
题意：
思路：对于每棵子树，只要确定了根节点，那么这棵树的值也就确定了。于是，可以来枚举每个
区间里根结点的情况来划分出它的左右子树。而每棵子树之间又是相互独立的，于是就想到了区间DP。
f[L][R]表示所有中序遍历[L,R]这一段的二叉树的所有方案。
假设根节点是k，于是f[L][R]=f[L][K-1]*F[K+1][R]+w[K]]。
怎么记录方案数呢？
g[L][R]来记录[L,R]这一段的根节点，一旦根节点确定了，就可以知道它的左右子树了，就可以递归下去了。
然后题目要求要按最小字典序顺序输出，如果在[L,R]里面有多个最优解，那我们肯定希望根越靠左边取好，所以只需要在判断f[l][r]<score时不取等号就可实现。
#include<iostream>
using namespace std;
const int N=35,M=110;
int w[N];
int f[N][N],g[N][N];//g[L][R]记录这个区间的根结点
void dfs(int l,int r)//前序遍历
{
if(l>r) return;
int k=g[l][r];//这段区间的根节点k
cout<<k<<" ";
dfs(l,k-1);
dfs(k+1,r);
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
for(int len=1;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
if(len==1)
{
f[l][r]=w[l];
g[l][r]=l;
}
else
{
for(int k=l;k<=r;k++)//枚举根节点
{
int left=k==l?1:f[l][k-1];//左子树为空
int right=k==r?1:f[k+1][r];//右子树为空
int score=left*right+w[k];
if(f[l][r]<score)//这里不取等号，可以保证最后记录的方案是按字典序最小的来的
{
f[l][r]=score;
g[l][r]=k;
}
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
return 0;
}
