https://www.acwing.com/problem/content/481/
给定从1~n编号的n个节点和他们各自的权值,构造出一颗中序遍历为1~n的得分最大的二叉树,输出其得分和前序遍历。
得分规则具体如下:如果根节点既有左子树又有右子树,那么得分=左子树*右子树+根节点权值
如果左子树、右子树其中之一为空,则权值为1
如果两者皆为空,则得分为根节点权值。
根据中序遍历为1~n发现这是属于区间DP的问题。
套用区间DP模型。
此时只是解决了求出最大得分的问题。
第二问输出最终二叉树的前序遍历还没有得到解决。
DP问题记录路径可以在状态转移的时候记录一下,之后再输出就可以了。
这里是同样的思想,g [ i ] [ j ] 表示 i ~ j 的根节点是哪一个。
1 #include<iostream> 2 using namespace std; 3 const int N=35; 4 int w[N]; 5 int f[N][N],g[N][N]; 6 void dfs(int l,int r){ 7 if(l>r){ 8 return ; 9 } 10 cout<<g[l][r]<<" "; 11 dfs(l,g[l][r]-1); 12 dfs(g[l][r]+1,r); 13 } 14 int main(void){ 15 int n; 16 cin>>n; 17 for(int i=1;i<=n;i++){ 18 cin>>w[i]; 19 } 20 for(int len=1;len<=n;len++){ 21 for(int i=1;i+len-1<=n;i++){ 22 int j=i+len-1; 23 if(i==j) f[i][j]=w[i],g[i][j]=i;//长度为一 24 else{ 25 for(int k=i;k<=j;k++){ 26 int left= k==i ? 1:f[i][k-1]; 27 int right = k==j? 1:f[k+1][j]; 28 int score=w[k]+left*right; 29 if(score>f[i][j]){ 30 f[i][j]=score; 31 g[i][j]=k;//记录i~j的根 32 } 33 } 34 } 35 } 36 } 37 cout<<f[1][n]<<endl; 38 dfs(1,n); 39 return 0; 40 }