# 加分二叉树

subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

（1）tree的最高加分
（2）tree的前序遍历

``````5
5 7 1 2 10

``````

``````145
3 1 2 4 5

``````

``````#include<stdio.h>
#include<stdlib.h>
int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
void print(int start, int end)
{
if (start > end)
return;
if (start == end)
{
ans[++t] = start;
return;
}
ans[++t] = d[start][end];
print(start, d[start][end]-1);
print(d[start][end]+1, end);
}
int main()
{
int n, a[35] = {0}, i, j, k, l;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
f[i][i-1] = 1;
f[i][i] = a[i];
}
for (l = 2; l <= n; l++)
for (i = 1; i <= n; i++)
for (k = i; k <= i+l-1; k++)
{
j = i+l-1;
if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k])
{
f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
d[i][j] = k;
}
}
printf("%d\n", f[1][n]);
print(1, n);
for (i = 1; i < t; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[t]);
return 0;
}
/*

[状态]f[i][j]从结点i到j的最大加分值
[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)

``````

``````#include<stdio.h>
#include<stdlib.h>
int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
void print(int start, int end)
{
if (start > end)
return;
if (start == end)
{
ans[++t] = start;
return;
}
ans[++t] = d[start][end];
print(start, d[start][end]-1);
print(d[start][end]+1, end);
}
int main()
{
int n, a[35] = {0}, i, j, k, l;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
f[i][i-1] = 1;
f[i][i] = a[i];
}
for (l = 2; l <= n; l++)
for (i = 1; i <= n; i++)
for (k = i; k <= i+l-1; k++)
{
j = i+l-1;
if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k])
{
f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
d[i][j] = k;
}
}
printf("%d\n", f[1][n]);
print(1, n);
for (i = 1; i < t; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[t]);
return 0;
}
/*

[状态]f[i][j]从结点i到j的最大加分值
[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)

``````