题解——加分二叉树
关于jmr，他进集训队了（差距过大）
这道题是一道绿题（码量上），但思路上不乏是道好题。
Luogu传送门：P1040 加分二叉树
还是搬运一下题面吧：
设一个nn个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di,tree及它的每个子树都有一个加分，任一棵子树subtreesubtree（也包含treetree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。
若某个子树为空，规定其加分为11，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）treetree的最高加分
（2）treetree的前序遍历
注意： n <= 30
解题思路：
这道题有点类似于关于树形DP的转化
最初看见这个中序遍历还真的无从下手，但我们仔细想想，在中序遍历中，对于任意点 i 作为根节点, [ 1 , i-1 ]必定为其左子树 ,[ i+1 , r ]必为其右子树。 再推广一下，对于一段可能成为子树的区间，我们可以枚举改子树的根节点，然后用dfs返回的值更新最值。
关于更新：由于代码简单，就写代码中了。
求前序遍历，我们只需要在枚举出最值的时候记录当前根节点，在跑一遍dfs输出即可。
AC code:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s = 0 ;
char g = getchar() ;
while( g>'9'||g<'0')g=getchar() ;
while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ;
return s ;
}
const int MAXN = 32 ;
int root[ MAXN ][ MAXN ] , dp[ MAXN ][ MAXN ] , M , a[ MAXN ] ; //root数组记录根节点
int dfs( int l , int r ){
if( dp[ l ][ r ] )return dp[ l ][ r ] ; //记忆化
if( l > r )return 1 ;//边界 返回1
if( l == r ){ // 叶节点 返回当前叶节点权值
dp[ l ][ r ] = a[ l ] ;root[ l ][ r ] = l ;
return dp[ l ][ r ] ;
}
for( register int i = l ; i <= r ; ++i ){ //枚举子树根节点
int w = dfs( l , i-1 )*dfs( i+1 ,r )+a[ i ] ;
if( w > dp[ l ][ r ] )dp[ l ][ r ] = w , root[ l ][ r ] = i ;//updata
}
return dp[ l ][ r ] ;
}
void firt_( int l , int r )//先序输出
{
if ( l > r )return ;
printf ( "%d ",root[ l ][ r ] );
firt_( l , root[ l ][ r ]-1 ) ;
firt_( root[ l ][ r ] + 1 , r ) ;
}
int main(){
M = read() ;
for( register int i = 1 ; i <= M ; ++i )a[ i ] = read() ;
cout<<dfs( 1 , M )<<endl ;
firt_( 1 , M ) ;
return 0 ;
}
这道题将先序遍历和树上Dp的结合确实ssw02最早没想到