luoguP1040 [NOIP2003]加分二叉树

题目链接

看了y总的视频然后自己推了一遍

做法就是区间DP

• 几点需要注意的：
  千万别忘了开long long(因为题目中说了Ans <= 4,000,000,000）
  边界问题需要仔细考虑
  记录答案的先序排列和输出值得思考

贴一下代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 35;
ll n, w[N], f[N][N], g[N][N];

void print(int l, int r) {
	if(l > n || r < 1 || r < l) return;
	int root = g[l][r];
	if(l == r){//叶子节点，因为没有子树，输出后直接return
		cout << root << ' ';
		return;
	}
	cout << root << ' ';//不是叶子节点，输出当前区间的根节点
	print(l, root - 1);//递归输出左子树
	print(root + 1, r);//递归输出右子树
}

signed main() {
	cin >> n;
	for(int i = 1; i <= n ; i ++)
		cin >> w[i];
	
	for(int i = 1; i <= n ; i ++) {//一定要记得初始化
		f[i][i] = w[i];
		g[i][i] = i;
	}
	for(int len = 2; len <= n ; len ++)//枚举区间长度
		for(int l = 1; l + len - 1 <= n ; l ++){//枚举左端点
			int r = l + len - 1;//计算右端点
			for(int k = l; k <= r; k ++) {//枚举每个区间的根节点
				ll left = k == l ? 1 : f[l][k-1];//如果没有左子树，左子树的价值就是1
				ll right = k == r ? 1 : f[k+1][r];//如果没有右子树，右子树的价值就是1
				ll score = left * right + w[k];//计算总价值
				if(f[l][r] < score) {//用if更新答案，而不用max，方便记录，这里是`<`而不是`<=`因为先序遍历如果有多种要按字典序输出（luogu上没说这个条件，但是AcWing上说了）
					f[l][r] = score;//更新答案
					g[l][r] = k;//记录区间l~r的根节点
				}
			}
		}
	cout << f[1][n] << endl;
	print(1, n);	
	return 0;
}

要是还不懂就好好看看那两张图（两张内容是一样的）。