博客

传送门


看到二叉树，第一反应是区间dp

f[i][j]=max(f[i][k-1] * f[k+1][j] + f[k][k])，i<=k<=j

但是在实现的时候突然卡壳了，于是只能求助题解

区间dp的主要思路是迭代区间长度

这里可以将区间长度设为除根节点外子树的总节点数

因此 j=i+len

初始状态将i设为根节点，依次遍历i+1 – j的所有节点

由于存在子树为空的情况，因此要将l>r的分数初始化为1

用root[i][j]存储该子树的根

代码

#include <iostream>
using namespace std;
const int N = 35;
int f[N][N], root[N][N];
int n;
void print(int l, int r){
	if(l > r) return;
	cout<<root[l][r]<<" ";
	print(l, root[l][r] - 1);
	print(root[l][r] + 1, r);
}
int main(){
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin>>f[i][i];
		//对应空子树
		f[i][i - 1] = 1;
		//记录这棵子树的根节点
		root[i][i] = i;
	}
	//len代指f[i][j]代表的子树中除了根节点还剩多少节点
	for(int len = 1;len < n;len++){
		for(int i = 1;i + len <= n;i++){
			int j = i + len;
			//初始化令i作为根节点，左子树为空
			f[i][j] = f[i + 1][j] + f[i][i];
			root[i][j] = i;
			//遍历子树中剩下的其他节点，尝试以遍历到的节点为根
			for(int k = i + 1;k <= j;k++){
				if(f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]){
					f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
					root[i][j] = k;
				}
			}
		}
	}
	cout<<f[1][n]<<endl;
	print(1, n);
	return 0;
}