# 1238. 加分二叉树

$$dp(i, j) = \max_{k = i}^{j - 1}(dp(i, k) * dp(k + 1, j) + \text{node_points}(k))$$

#include "bits/stdc++.h"
using u32 = uint32_t;
using u64 = uint64_t;

struct DpRecord {
u64 point = 0;
std::vector<u32> preorder_traversal;
};

int main() {
u32 n;
std::cin >> n;
std::vector<u32> node_points(n + 1);
for (u32 i = 1; i <= n; ++i) {
std::cin >> node_points[i];
}
std::vector dp(n + 1, std::vector<DpRecord>(n + 1));
for (u32 i = 1; i <= n; ++i) {
// Special case for leaves.
dp[i][i].point = node_points[i];
dp[i][i].preorder_traversal.push_back(i);
}
for (u32 span_size = 2; span_size <= n; ++span_size) {
for (u32 i = 1, j = i - 1 + span_size; j <= n; ++i, ++j) {
u32 root;
u64 potential_max;
{ // Special case for borders.
auto const kIAsRoot = dp[i + 1][j].point + node_points[i];
auto const kJAsRoot = dp[i][j - 1].point + node_points[j];
if (kIAsRoot < kJAsRoot) {
root = j;
potential_max = kJAsRoot;
} else {
root = i;
potential_max = kIAsRoot;
}
}
for (u32 k = i + 1; k < j; ++k) {
auto const kPoint = dp[i][k - 1].point * dp[k + 1][j].point + node_points[k];
if (potential_max < kPoint) {
potential_max = kPoint;
root = k;
}
}
dp[i][j].point = potential_max;
auto& vec = dp[i][j].preorder_traversal;
vec.push_back(root);
for (auto const id : dp[i][root - 1].preorder_traversal) {
vec.push_back(id);
}
for (auto const id : dp[root + 1][j].preorder_traversal) {
vec.push_back(id);
}
}
}
std::cout << dp[1][n].point << '\n';
for (auto const id : dp[1][n].preorder_traversal) {
std::cout << id << ' ';
}
std::cout << '\n';
}


### include

using namespace std;
const int maxn=35;
long long int score[maxn][maxn];
int vi[maxn];
int root[maxn][maxn];//用来存l-r之间的根节点
void printt(int l,int r)
{
if(l>r) return;
cout<<root[l][r]<<" ";
printt(l,root[l][r]-1);
printt(root[l][r]+1,r);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
memset(score,0,sizeof(score));
for(int i=1;i<=n;i++) cin>>vi[i];
for(int i=1;i<=n;i++) root[i][i]=i;
for(int i=1;i<=n;i++) score[i][i]=vi[i];
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<=j;k++){
if(k==i){
if(score[i][j]<score[k+1][j]+vi[k]){
root[i][j]=k;
score[i][j]=score[k+1][j]+vi[k];
}
}
else if(k>i&&k<j){
if(score[i][j]<score[i][k-1]*score[k+1][j]+vi[k]){
root[i][j]=k;
score[i][j]=score[i][k-1]*score[k+1][j]+vi[k];
}
}
else if(k==j){
if(score[i][j]<score[i][k-1]+vi[k]){
root[i][j]=k;
score[i][j]=score[i][k-1]+vi[k];
}
}
}
}
}
cout<<score[1][n]<<endl;
printt(1,n);
}


\cpp
\ code...
\


（上面的没有反斜线）