NOIP2003加分二叉树
题目描述 Description
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空
子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入描述 Input Description
第1行：一个整数n（n<=30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数<=100）
输出描述 Output Description
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
样例输入 Sample Input
5
5 7 1 2 10
样例输出 Sample Output
145
3 1 2 4 5
数据范围及提示 Data Size & Hint
n（n<=30)
分数<=100
题解
用f(i,j)表示 i 到 j 段的最大加分，p(i,j)表示根节点
则\(f(i,j)=max \{f(i,k-1)*(f(k+1,j)+w_k \}\)
输出时递归输出即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 998244353 #define N 100005 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,v[35]; int f[35][35],p[35][35]; int dp(int l,int r) { if(l>r)return 1; if(f[l][r]!=-1)return f[l][r]; if(l==r) { p[l][r]=l; return v[l]; } int &ans=f[l][r],&pos=p[l][r]; for(int i=l;i<=r;i++) if(dp(l,i-1)*dp(i+1,r)+v[i]>ans) { ans=dp(l,i-1)*dp(i+1,r)+v[i]; pos=i; } return ans; } void print(int l,int r) { int pos=p[l][r]; printf("%d ",pos); if(l<=pos-1)print(l,pos-1); if(pos+1<=r)print(pos+1,r); } int main() { memset(f,-1,sizeof(f)); n=read(); for(int i=1;i<=n;i++)v[i]=read(); printf("%d\n",dp(1,n)); print(1,n); return 0; } |
Subscribe
计数器 9734137
OI 课件=>
OI 课件=>