P1040 加分二叉树

admin

https://www.luogu.org/problemnew/show/P1040

题目描述
设一个 nn 个节点的二叉树tree的中序遍历为（ 1,2,3,…,n），其中数字 1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 ii 个节点的分数为 di,tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree本身）的加分计算方法如下：

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

若某个子树为空，规定其加分为 1 ，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（ 1,2,3,…,n ）且加分最高的二叉树 tree 。要求输出；

（1） tree 的最高加分

（2） tree 的前序遍历

输入输出格式
输入格式：
第 1行： 1 个整数 n(n<30) ，为节点个数。

第 2 行： n 个用空格隔开的整数，为每个节点的分数（分数 <100 ）。

输出格式：
第 1 行：1 个整数，为最高加分（Ans ≤4,000,000,000 ）。

第 2 行： n 个用空格隔开的整数，为该树的前序遍历。

输入输出样例
输入样例#1：
5
5 7 1 2 10
输出样例#1：
145
3 1 2 4 5

universehyf

区间DP

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
4. int n,a[110];
   
5. int f[110][110][2];
   
6. void dfs(int l,int r)
   
7. {
   
8.     if(l>r) return;
   
9.     if(l==r) {cout<<l<<" ";return;}
   
10.     cout<<f[l][r][1]<<" ";
    
11.     dfs(l,f[l][r][1]-1);
    
12.     dfs(f[l][r][1]+1,r);
    
13. }
    
14. int main()
    
15. {
    
16.     cin>>n;FOR(i,1,n) cin>>a[i];
    
17.     FOR(i,1,n) f[i][i][0]=a[i];
    
18.     FOR(i,2,n) FOR(j,1,n-i+1) FOR(k,j,i+j-1)
    
19.     {
    
20.         if(!f[j][k-1][0]) f[j][k-1][0]=1;if(!f[k+1][i+j-1][0]) f[k+1][i+j-1][0]=1;
    
21.         if(f[j][k-1][0]*f[k+1][i+j-1][0]+a[k]>f[j][i+j-1][0])
    
22.         {
    
23.             f[j][i+j-1][0]=f[j][k-1][0]*f[k+1][i+j-1][0]+a[k];
    
24.             f[j][i+j-1][1]=k;
    
25.             ///cout<<j<<" "<<i+j-1<<" "<<k<<" "<<f[j][i+j-1][0]<<' '<<f[j][i+j-1][1]<<endl;
    
26.         }
    
27.     }
    
28.     cout<<f[1][n][0]<<endl;
    
29.     dfs(1,n);
    
30.     return 0;
    
31. }

复制代码

倚窗倾听风吹雨

区间dp，f（i，j）表示i~j之间组成子树的最大值；

1. #include<iostream>
   
2. using namespace std;
   
3. int n,ans,a[30],f[30][30],gra[30],root[30][30];
   
4. void print(int l,int r)
   
5. {
   
6.     if(l>r)return;
   
7.     if(l==r)
   
8.     {
   
9.         cout<<l<<" ";
   
10.         return;
    
11.     }
    
12.     cout<<root[l][r]<<" ";
    
13.     print(l,root[l][r]-1);
    
14.     print(root[l][r]+1,r);
    
15. }
    
16. int main()
    
17. {
    
18.     cin>>n;
    
19.     for(int i=1;i<=n;i++)
    
20.     {
    
21.         cin>>gra[i];
    
22.         a[i]=i;
    
23.         f[i][i]=gra[i];
    
24.         f[i][i-1]=1;
    
25.     }
    
26.     for(int i=n;i>=1;i--)
    
27.         for(int j=i+1;j<=n;j++)
    
28.             for(int k=i;k<=j;k++)
    
29.                 if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])
    
30.                 {
    
31.                     f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
    
32.                     root[i][j]=k;
    
33.                 }
    
34.     cout<<f[1][n]<<endl;
    
35.     print(1,n);
    
36.     return 0;
    
37. }

复制代码