当看到这个的时候,我是不知道怎么遍历这个二叉树(尽管给我了中序遍历)
后来我才知道一个中序遍历是无法确定二叉树的
老规矩
老师的视频网址:
老师用了区间dp;
dp[l][r]是左边界l,右边界r的最大加分同时还需要设一个k表示根节点,然后dp[l][k-1]表示左子树最大加分,dp[k+1][r]表示有指数最大加分。然后遍历这一区间最大的加分就可,题目中要求输出一个前序的序列,那我们把每一个最大区间也就是dp[l][k-1]*dp[k+1][r]+w[k]的根节点记下来就好了用g[l][r]来保存.最后说一下题意
对与一个根节点1.若只有一个子树,则根的加分为子树的分值*1+根的分数。2.若是有两个子树,则根的加分为左子树分值*右子树分值+根的分数3.若没有子树,则根的加分为根的分数本身。最后说下代码吧,也不是很长
#include<iostream>using namespace std;const int N=35;int w[N],dp[N][N],g[N][N];void print(int l,int r)//输出前序 根、左、右{ if(l>r) return; cout<<g[l][r]<<" "; print(l,g[l][r]-1); print(g[l][r]+1,r); return;}int main(void){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int len=1;len<=n;len++) for(int l=1;l+len-1<=n;l++) { int r=l+len-1; if(len==1) { dp[l][r]=w[l]; g[l][r]=l; } else { for(int k=l;k<=r;k++) { int left=k==l?1:dp[l][k-1]; int right=k==r?1:dp[k+1][r]; int score=left*right+w[k]; if(score>dp[l][r]) { dp[l][r]=score; g[l][r]=k; } } } } cout<<dp[1][n]<<endl; print(1,n);}