原題來自：NOIP 2003

設(shè)一個 n 個節(jié)點的二叉樹 tree 的中序遍歷為 (1,2,3,?,n)，其中數(shù)字 1,2,3,?,n 為節(jié)點編號。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)），記第 i 個節(jié)點的分?jǐn)?shù)為 di ，tree 及它的每個子樹都有一個加分，任一棵子樹 subtree（也包含 tree 本身）的加分計算方法如下：

記 subtree 的左子樹加分為 l，右子樹加分為 r，subtree 的根的分?jǐn)?shù)為 a，則 subtree 的加分為：

l×r+a
若某個子樹為空，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。不考慮它的空子樹。

試求一棵符合中序遍歷為 (1,2,3,?,n) 且加分最高的二叉樹 tree。

要求輸出：

1、tree 的最高加分；

2、tree 的前序遍歷。

第一行一個整數(shù) n 表示節(jié)點個數(shù)；

第二行 n 個空格隔開的整數(shù)，表示各節(jié)點的分?jǐn)?shù)。

第一行一個整數(shù)，為最高加分 b；

第二行 n 個用空格隔開的整數(shù)，為該樹的前序遍歷。

數(shù)據(jù)范圍與提示：

對于 100% 的數(shù)據(jù)，n<30,b<100，結(jié)果不超過 4×10⁹ 。

信息學(xué)一本通 動態(tài)規(guī)劃