P1040加分二叉树

关于我必须刷dp这回事。

题意：

一颗有$n$个节点的树的中序遍历为$(1,2,3,\dots,n)$，现定义一个根节点的分数为左子树分数*右子树分数+该点分数，定义空子树分数为1，求这棵树最大的分数，输出最大分数和这棵树的前序遍历。

题解：

在想方程之前，先想想二叉树的遍历的方式，中序的遍历为左根右，这点很重要，那我们就可以从后往前逆着推这个区间以k为根的最大值，转移方程为：

$dp_{i,j}=max\{k\in[i,j]|dp[i][k-1]*dp[k+1][j]+a[k]\}$，并且在更新的时候更新一下每个区间的根节点，用$root[i][j]$表示即可。

//I am so vegetable
//#define err
#include<bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define _rfor(type,i,a,b) for(type i = (a);i>(b);--i)
#define endl '\n'
typedef long long ll;

int a[35],root[35][35];
ll dp[35][35];
void dfs(int l,int r){
  if(l>r)return;
  cout<<root[l][r]<<' ';
  dfs(l,root[l][r]-1);
  dfs(root[l][r]+1,r);
}
signed main() {
  //ifstream cin("E:\\acm dream\\in.in");
  //ofstream cout("E:\\acm dream\\out.out");
  FIO;
  #ifdef err
  double be = clock();
  #endif

  int n;cin>>n;
  _for(int,i,1,n+1)cin>>a[i];
  _for(int,i,1,n+1){
    root[i][i]=i;
    dp[i][i]=a[i];
    dp[i][i-1]=1;
  }
  _rfor(int,i,n,0){
    _for(int,j,i+1,n+1){
      _for(int,k,i,j+1){
        if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+a[k]){
          dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
          root[i][j]=k;
        }
      }
    }
  }
  cout<<dp[1][n]<<endl;
  dfs(1,n);

  #ifdef err
  double en = clock();
  cout<<"time: "<<fixed<<setprecision(8)<<en-be;
  #endif
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2021/04/16/P1040加分二叉树/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！