[NOIP 2003 提高组] 加分二叉树

知识点

区间动态规划、二叉树、方案构造

解题思路

f[l][r]表示中序区间[l,r]的最大加分。单节点直接为该节点分数；空子树分数1。长度至少2时枚举根k，左右区间互相独立，取f[l][k-1]·f[k+1][r]+d[k]的最大值并记录根。按根、左、右顺序递归恢复前序。

正确性说明

任何合法树的根k把固定中序切成左右连续区间。分数均为正，因此分别取两侧最大值能使乘积最大；枚举所有根覆盖所有结构。区间长度归纳给出最优分数，记录根恢复出的树恰达到该值。叶子按题目单独计分。

易错点

叶子不能误算为1·1+d；答案可能超过有符号32位；最优树可能不唯一，本地检查器接受任意合法最优前序。

复杂度

时间O(n³)，空间O(n²)，恢复O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
long long f[31][31];int root[31][31];void out(int l,int r){if(l>r)return;int k=root[l][r];cout<<k<<' ';out(l,k-1);out(k+1,r);}int main(){int n;cin>>n;long long a[31];for(int i=1;i<=n;i++){cin>>a[i];f[i][i]=a[i];root[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++){long long v=(k==l?1:f[l][k-1])*(k==r?1:f[k+1][r])+a[k];if(v>f[l][r])f[l][r]=v,root[l][r]=k;}}cout<<f[1][n]<<'\n';out(1,n);cout<<'\n';}