P1040 [NOIP2003 提高組] 加分二叉樹 - 洛谷 | 電腦科學教育新生態 (luogu.com.cn) 題意：給你一顆中序遍歷為1到n的二叉樹，和每個節點的val。樹的值=左子樹的值×右子樹的值+根的val，空樹值為1，求整個樹最大值和這個值樹的前序遍歷。 題解：區間dp。dp[l] ...
P1040 [NOIP2003 提高組] 加分二叉樹 - 洛谷 | 電腦科學教育新生態 (luogu.com.cn)
題意：給你一顆中序遍歷為1到n的二叉樹，和每個節點的val。樹的值=左子樹的值×右子樹的值+根的val，空樹值為1，求整個樹最大值和這個值樹的前序遍歷。
題解：區間dp。dp[l][r]表示最大值，root[l][r]表示最大值的根，枚舉區間然後枚舉根，根據題目中的計算公式搞最大值。
樹形dp。一樣的dp[l][r]表示子樹罷了。
多想想，一步步討論就好了，關鍵是找能做出答案的狀態表示再想轉移方程。
int n,a[N],dp[N][N],rt[N][N];void pre_ans(int l,int r){
if(l>r) return;
cout<<rt[l][r]<<" ";
pre_ans(l,rt[l][r]-1);
pre_ans(rt[l][r]+1,r);
}
void solve(){
cin>>n;
rep(i,1,n+1) cin>>a[i],dp[i][i]=a[i],rt[i][i]=i;
for(int len=1;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r = l+len-1;
dp[l][r] = dp[l + 1][r] + dp[l][l];//左子樹為空
rt[l][r]=l;
for(int k=l+1;k<r;k++){//左子樹的節點數 枚舉子樹的根
if(dp[l][r]<dp[l][k-1]*dp