华师一附中OI组

标题: P1040 加分二叉树 [打印本页]
作者: admin    时间: 2018-6-29 18:36
标题: P1040 加分二叉树
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
作者: 倚窗倾听风吹雨    时间: 2018-9-9 09:58
本帖最后由 倚窗倾听风吹雨 于 2018-9-9 10:27 编辑

区间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. }
复制代码





作者: universehyf    时间: 2018-10-3 23:39
区间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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2