# 11077: 【原1077】加分二叉树

### 题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1077

## Description

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

（1）tree的最高加分

（2）tree的前序遍历

tree的最高加分。

tree的前序遍历。

## Sample Input

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

## Sample Output

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

## FineArtz's solution

``````/* 加分二叉树 */
#include <iostream>
#include <cstring>
using namespace std;

int n;
int a[35] = {0}, r[35][35] = {0};
int f[35][35] = {0};

int calc(int l, int h){
if (l > h)
return 1;
if (f[l][h] >= 0)
return f[l][h];
if (l == h){
r[l][h] = l;
f[l][h] = a[l];
return f[l][h];
}
for (int k = l; k <= h; ++k){
int p = calc(l, k - 1), q = calc(k + 1, h);
if (f[l][h] < p * q + a[k]){
f[l][h] = p * q + a[k];
r[l][h] = k;
}
}
return f[l][h];
}

void ldr(int l, int h){
if (l > h)
return;
cout << r[l][h] << ' ';
ldr(l, r[l][h] - 1);
ldr(r[l][h] + 1, h);
}

int main(){
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
memset(f, -1, sizeof(f));
memset(r, -1, sizeof(r));
calc(1, n);
cout << f[1][n] << endl;
ldr(1, n);
cout << endl;
return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 100;
int DP[maxN][maxN], path[maxN][maxN], tree[maxN] = {0};

int search(int, int);

void output(int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n;

cin >> n;
for (int i = 1; i <= n; i++) {
cin >> tree[i];
}
cout << search(1, n) << '\n';
output(1, n);

return 0;
}

int search(int left, int right) {
if (left > right) {
return 1;
} else if (left == right) {
DP[left][right] = tree[left];
path[left][right] = left;
} else if (DP[left][right] > 0) {
return DP[left][right];
} else {
for (int i = left; i <= right; i++) {
int x = search(left, i - 1) * search(i + 1, right) + tree[i];
if (x > DP[left][right]) {
DP[left][right] = x;
path[left][right] = i;
}
}
}

return DP[left][right];
}

void output(int left, int right) {
if (left > right) {
return;
}

cout << path[left][right] << ' ';
output(left, path[left][right] - 1);
output(path[left][right] + 1, right);
}
``````

## q4x3's solution

``````/**
* dp
* rt[l][r] 表示区间[l, r]的根
* f[l][r] 表示区间[l, r]的加分
**/
#include <iostream>
#include <stdio.h>

using namespace std;

int n, val[40], rt[40][40], f[40][40];

void dfs(int l, int r) {
if(l > r) return;
printf("%d ", rt[l][r]);
dfs(l, rt[l][r] - 1);
dfs(rt[l][r] + 1, r);
return;
}

int main() {
scanf("%d", &n);
for(int i = 1;i <= n;++ i) {
scanf("%d", &val[i]);
}
for(int i = 1;i <= n;++ i) {
rt[i][i] = i;
f[i][i] = val[i];
f[i][i - 1] = 1;
}
for(int i = 2;i <= n;++ i) {
for(int l = 1;l + i - 1 <= n;++ l) {
int r = l + i - 1;
for(int j = l;j <= r;++ j) {
if(f[l][j - 1] * f[j + 1][r] + val[j] > f[l][r]) f[l][r] = f[l][j - 1] * f[j + 1][r] + val[j], rt[l][r] = j;
}
}
}
printf("%d\n", f[1][n]);
dfs(1, n);
putchar('\n');
return 0;
}
``````

## victrid's solution

``````#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
long long dp[35][35] = {};
int root[35][35]     = {};
long long search(int l, int r) {
if (l > r)
return 1;
if (dp[l][r] != 0)
return dp[l][r];
for (int i = l; i <= r; i++) {
long long pas = search(l, i - 1) * search(i + 1, r) + search(i, i);
if (pas > dp[l][r]) {
dp[l][r]   = pas;
root[l][r] = i;
}
}
return dp[l][r];
}
bool isfirst = false;
void findpath(int l, int r) {
if (l > r)
return;
if (l == r) {
if (isfirst)
putchar(' ');
isfirst = true;
printf("%d", l);
return;
}
if (isfirst)
putchar(' ');
isfirst = true;
printf("%d", root[l][r]);
findpath(l, root[l][r] - 1);
findpath(root[l][r] + 1, r);
return;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &(dp[i][i]));
}
printf("%lld\n", search(1, n));
findpath(1, n);
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
using namespace std;

int path[35][35], p;
int dp[35][35], a[35];

int dfs(int l, int r) {

if (dp[l][r] > 0) return dp[l][r];
if (l > r) return 1;
if (l == r) {
dp[l][r] = a[l];
path[l][r] = l;
}
else
for (int i = l; i <= r; ++i) {
int x = dfs(l, i - 1) * dfs(i + 1, r) + a[i];
if (x > dp[l][r]) {
dp[l][r] = x;
path[l][r] = i;
}
}
return dp[l][r];
}

void print (int l, int r) {

if (l > r) return;
if (p++) cout << " " << path[l][r];
else cout << path[l][r];
print(l, path[l][r] - 1);
print(path[l][r] + 1, r);
}

int main() {

int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
cout << dfs(1, n) << endl;
p = 0;
print(1, n);
return 0;
}
``````