题目描述
设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
输入输出格式
输入格式：
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
输出格式：
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
输入样例#1：
5
5 7 1 2 10
输出样例#1
145
3 1 2 4 5
dp[i][j]表示中序遍历[i,j]的最大得分,所以dp[i][j]=max(dp[i][k-1]*dp[i][k+1]+a[k])
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; int dp[35][35],a[35],pre[35][35],n; template <class T> void read(T &x) { x=0;int f=0; char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-'); ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} x=f?-x:x; return ; } void mid(int l,int r)//前序遍历 { if(l==r) { printf("%d ",l); return ; } if(r==l+1) { printf("%d %d ",l,l+1); return ; } printf("%d ",pre[l][r]); mid(l,pre[l][r]-1); mid(pre[l][r]+1,r); } int main() { int i,j,len,k; read(n); for(i=1;i<=n;i++) { read(a[i]); dp[i][i]=a[i]; } for(i=1;i+2-1<=n;i++)//特判长度为二 { j=i+2-1; dp[i][j]=dp[i][i]+dp[j][j]; pre[i][j]=i; } for(len=3;len<=n;len++)//dp { for(i=1;i+len-1<=n;i++) { j=len+i-1; k=i+1; dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k]; pre[i][j]=k; for(k=i+2;k<j;k++) { if(dp[i][k-1]*dp[k+1][j]+a[k]>dp[i][j])//更新 { pre[i][j]=k; dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k]; } } } } printf("%d ",dp[1][n]); mid(1,n);//rock and roll~ return 0; }