題目

題目描述

設一個 n n n 個節點的二叉樹 tree \text{tree} tree 的中序遍歷為 ( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n) (1,2,3,…,n)，其中數字 1 , 2 , 3 , … , n 1,2,3,\ldots,n 1,2,3,…,n 為節點編號，每個節點都有一個分數（均為正整數），記第 i i i 個節點的分數為 d i d_i di?， tree \text{tree} tree 及它的每個子樹都有一個加分，任一棵子樹 subtree \text{subtree} subtree（也包含 tree \text{tree} tree 本身）的加分計算方法如下：

subtree \text{subtree} subtree 的左子樹的加分 × subtree \times \text{subtree} ×subtree 的右子樹的加分 + subtree + \text{subtree} +subtree的根的分數，

若某個子樹為空，規定其加分為 1 1 1，葉子的加分就是葉節點本身的分數，不考慮它的空子樹，

試求一棵符合中序遍歷為 ( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n) (1,2,3,…,n) 且加分最高的二叉樹 tree \text{tree} tree，要求輸出

tree \text{tree} tree 的最高加分，

tree \text{tree} tree 的前序遍歷，

輸入格式

第 1 1 1 行 1 1 1 個整數 n n n，為節點個數，

第 2 2 2 行 n n n 個用空格隔開的整數，為每個節點的分數

輸出格式

第 1 1 1 行 1 1 1 個整數，為最高加分（ A n s ≤ 4 , 000 , 000 , 000 Ans \le 4,000,000,000 Ans≤4,000,000,000），

第 2 2 2 行 n n n 個用空格隔開的整數，為該樹的前序遍歷，

輸入輸出樣例

輸入

5
5 7 1 2 10

輸出

145
3 1 2 4 5

說明/提示

n < 30 n< 30 n<30，

分數 < 100 <100 <100，

題解

1.

因為中序遍歷為 ( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n) (1,2,3,…,n)，所以我們可以得到每一棵子樹都滿足：左子樹各節點序號<根<右子樹各節點序號
所以想到區間DP

2.DP

1.狀態

我們設 d p [ i ] [ j ] dp[i][j] dp[i][j]表示從 i i i ~ j j j生成樹的最大加分

2.階段

len唄，區間DP基本操作

3.轉移

列舉根節點 k ( l < k < r ) k(l <k<r) k(l<k<r)， d p [ l ] [ r ] = m i n ( d p [ l ] [ r ] , d p [ l ] [ k ? 1 ] ? d p [ k + 1 ] [ r ] + a [ k ] ) dp[l][r]=min(dp[l][r],dp[l][k-1]*dp[k+1][r]+a[k]) dp[l][r]=min(dp[l][r],dp[l][k?1]?dp[k+1][r]+a[k])

for(int len=1;len<n;++len){
        for(int l=1;l+len<=n;l++){
            int r=l+len;
            dp[l][r]=dp[l+1][r]+a[l];
            root[l][r]=l;
            for(int k=l+1;k<r;++k){
                if(dp[l][r]<dp[l][k-1]*dp[k+1][r]+a[k]){
                    dp[l][r]=dp[l][k-1]*dp[k+1][r]+a[k];
                    root[l][r]=k;
                }
            }
        }
    }

4.輸出路徑

每次轉移的時候保存一下根節點，有了根節點不就好做了嗎\ (^o^)/~

void print(int l,int r){
    if(l>r){
    	return;
	}
    printf("%d ",root[l][r]);
    if(l==r){
    	return;
	}
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}

5.代碼

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=35;
int n; 
int dp[MAXN][MAXN];
int a[MAXN];
int root[MAXN][MAXN];
void print(int l,int r){
    if(l>r){
    	return;
	}
    printf("%d ",root[l][r]);
    if(l==r){
    	return;
	}
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
    	dp[i][i]=a[i];
		dp[i][i-1]=1;
		root[i][i]=i;
	}
    for(int len=1;len<n;++len){
        for(int l=1;l+len<=n;l++){
            int r=l+len;
            dp[l][r]=dp[l+1][r]+a[l];
            root[l][r]=l;
            for(int k=l+1;k<r;++k){
                if(dp[l][r]<dp[l][k-1]*dp[k+1][r]+a[k]){
                    dp[l][r]=dp[l][k-1]*dp[k+1][r]+a[k];
                    root[l][r]=k;
                }
            }
        }
    }
    printf("%d\n",dp[1][n]);
    print(1,n);
    return 0;
}