/*
一道披着树形dp的区间dp666666
我们可以用记忆化递归搜索来动态规划一下
我们知道因为该二叉树的中序遍历为1....n
根节点的选取其实有无数种情况
那我们就递归枚举所有可能的根节点比较所能得到的最大值
我们设f[i][j]表示i结点到j结点的加分二叉树所能达到的最大加分值
root[i][j]=k表示该最大加分值是在根节点为k的时候达到的
那么我们就可以得到下面的状态转移方程
f[i][j]=max(f[i][k-1]*f[k+1][j]+d[k],i<=k<=j)
注意边界子树为空时加分值为1
那么我们就记忆化搜索一下就好了
再来考虑一下输出，要输出前序遍历
那么我们想一下怎么输出前序遍历？
对于f[1][n]找到其最优解的时候的根节点root[1][n]
然后再根据这个根节点将树分成二叉树，然后再递归找到根节点输出
边界是子树为空的时候~
问题就解决了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int a[31];
int f[31][31];
int root[31][31];

int dfs(int l,int r)
{
    int ans=-1;
    int node=-1;
    if(f[l][r]!=-1)
        return f[l][r];
    else    if(l>r)
        return f[l][r]=1;
    else    if(l==r)
    {
        root[l][r]=l;
        return f[l][r]=a[l];
    }
    else
    {
        for(int i=l;i<=r;i++)
        {
            int temp=dfs(l,i-1)*dfs(i+1,r)+a[i];
            if(ans<temp)
            {
                ans=temp;
                node=i;
            }
        }
    }
    root[l][r]=node;
    return f[l][r]=ans;
}

void print(int l,int r)
{
    if(l<=r)
    {
        cout<<root[l][r]<<" ";
        print(l,root[l][r]-1);
        print(root[l][r]+1,r);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(f,-1,sizeof(f));
    memset(root,-1,sizeof(root));
    dfs(1,n);
    cout<<f[1][n]<<endl;
    print(1,n);
    return 0;
}
     

【美妙的区间DP与树的遍历的入门】

#include<stdio.h>
#include<iostream>
#define go(i,a,b) for(int i=a;i<=b;i++) 
#define ro(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int f[35][35],d[35][35],ans[35],t,a[35],n;
void P(int l, int r){
     if(l>r)return;if(l==r){ans[++t]=l;return;}
     ans[++t]=d[l][r];P(l,d[l][r]-1);P(d[l][r]+1,r);}
int main(){
     scanf("%d",&n);
     go(i,1,n)scanf("%d",&a[i]),
     f[i][i-1]=1,f[i][i]=a[i];
     go(l,2,n)go(i,1,n){
     int j=i+l-1;go(k,i,i+l-1){
     int tmp=f[i][k-1]*f[k+1][j] + a[k];
     if (f[i][j]<tmp)f[i][j]=tmp,d[i][j]=k;}}
     
     printf("%d\n",f[1][n]);P(1,n);
     go(i,1,t)printf("%d ",ans[i]);
     printf("\n");
 }

-Paul_Guderian

/*
进行区间dp，计算每一个区间树的最大值。在区间内枚举根的位置，计算最大值，用f保存，根用r保存。
最后是树的先序遍历。 
*/
#include<cstdio>
int f[33][33],r[33][33],a[33],n;
void write(int p,int q)              //先序遍历。 
{
    if (p>q||p<1||q>n) return;       //空树，退出。 
    printf("%d ",r[p][q]);           //挖根节点。 
    write(p,r[p][q]-1);              //遍历左子。 
    write(r[p][q]+1,q);              //遍历右子。 
    return;
}
int main()
{
    int i,j,k,t,s;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i][i]=a[i]; r[i][i]=i;     //只有根。 
        f[i][i-1]=1;                 //空树，置为1。 
    }
    f[n+1][n]=1;                     //同上，dp时会取到这些值。 
    for (i=1;i<n;i++)                //区间大小从(i+1)到n。 
        for (j=1;j<=n-i;j++)         //起始位置。 
            for (k=j;k<=j+i;k++)     //根。 
            {
                t=a[k]+f[j][k-1]*f[k+1][j+i];
                if (t>f[j][j+i]) {f[j][j+i]=t; r[j][j+i]=k;}
            }
    printf("%d\n",f[1][n]);
    write(1,n);
    return 0;
}

一道区间DP，代码还算短吧。

状态：F[l][r] 表示以(l, r)为内部节点的子树取得最大值的最优解情况，转移只需枚举子树的根就行。
方程：F[l][r] = F[l][i-1] * F[i+1][r] + Ai
特殊的，当l > r时， F[l][r] = 1 (空树)
特殊的，当l = r时，F[l][r] = Al

提示：1.为什么一道树形DP的转移最后变成了区间DP的形式，这主要依赖于中序遍历的性质，及结构一定为左根右，形成了一个可递归的形式。
2.输出的方式很明显遵循了根左右，这体现的是先序遍历的性质。

#include <cstdio>
#include <iostream>
using namespace std;
int N;
int A[35];
int F[35][35], R[35][35];
int DP (int l, int r) {
    
    if (r<l) return 1;
    if (F[l][r]) return F[l][r];
    for(int i=l; i<=r; i++) {
        int val=DP(l, i-1)*DP(i+1, r)+A[i];
        if (l==r) val=A[i];
        if (val>F[l][r]) {
            R[l][r]=i;
            F[l][r]=val;
        } 
    }
    return F[l][r];
     
}
void PT (int l, int r) {
    
    if (l<=r) {
        int pot=R[l][r];
        cout << pot << " ";
        if (l!=r) {
            PT(l, pot-1);
            PT(pot+1 ,r);
        }
    }
    
}
int main () {
    
    cin >> N;
    for( int i=1; i<=N; i++)
        scanf("%d", &A[i]);
    DP(1, N); 
    cout << F[1][N] << endl;    
    PT(1, N);
    return 0;    
    
}

#include<bits/stdc++.h>
using namespace std;

int n,v[39],f[47][47],i,j,k,root[49][49];
void print(int l,int r){
    if(l>r)
        return;
    if(l==r){
        printf("%d ",l);
        return;
    }
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}

int main() {
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>v[i];
    for(i=1; i<=n; i++){
        f[i][i]=v[i];
        f[i][i-1]=1;
    }
    for(i=n; i>=1; i--)
        for(j=i+1; j<=n; j++)
            for(k=i; k<=j; k++)
                if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    root[i][j]=k;
                }
    printf("%d\n",f[1][n]);
    print(1,n);
    return 0;
}

interesting

#include<cstdio>
#include<algorithm>
#include<cstring>
#define max_n 55
using namespace std;
int n,w[max_n],j,dp[max_n][max_n],root[max_n][max_n];
inline void print(int l,int r)
{
    if(l>r) return ;
    printf("%d ",root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(register int l=1;l<=n;l++)
        for(register int i=1;i+l-1<=n;i++)
        {
            j=i+l-1;
            for(register int k=i;k<=j;k++)
                if(i==j) dp[i][j]=w[i],root[i][j]=i;
                else if(k==i) 
                {
                    if(dp[i][j]<dp[i+1][j]+w[k])
                        dp[i][j]=dp[i+1][j]+w[k],root[i][j]=k;
                }
                else if(k==j) 
                {
                    if(dp[i][j]<dp[i][j-1]+w[k])
                        dp[i][j]=dp[i][j-1]+w[k],root[i][j]=k;
                }
                else 
                {
                    if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+w[k])
                        dp[i][j]=dp[i][k-1]*dp[k+1][j]+w[k],root[i][j]=k;
                }
        }
    printf("%d\n",dp[1][n]);
    print(1,n);
    return 0;
}

#include <iostream>
using namespace std;
int n,a[35];
long long f[35][35],p[35][35];
void pre_order(int l,int r)
{
if(l==r)
{
cout<<l<<" ";
}
else if(l==r-1)
{
cout<<l<<" "<<r<<" ";
}
else
{
cout<<p[l][r]<<" ";
pre_order(l,p[l][r]-1);
pre_order(p[l][r]+1,r);
}

}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{

cin>>a[i];
f[i][i]=a[i];
}

for(int k=1;k<n;k++)
{
for(int i=1;i<=n-k;i++)
{

f[i][i+k]=f[i][i]+f[i+1][i+k];
p[i][i+k]=i;
long long data;
for(int j=i+1;j<i+k;j++)
{
data=f[i][i+k];
f[i][i+k]=max(f[i][i+k],f[i][j-1]*f[j+1][i+k]+f[j][j]);
if(data!=f[i][i+k])
p[i][i+k]=j;
}
data=f[i][i+k];
f[i][i+k]=max(f[i][i+k],f[i][i+k-1]+f[i+k][i+k]);
if(data!=f[i][i+k])
p[i][i+k]=i+k;
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=i+1;j<=n;j++)
// {
// cout<<p[i][j]<<endl;
// }
// }
// system("pause");
cout<<f[1][n]<<endl;
pre_order(1,n);
// system("pause");
return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[35], g[35][35];
ll f[35][35];

void print(int l, int r){
if(l==r){ cout<<l<<' '; return; }
if(l>r) return;
int tmp=g[l][r];
cout<<tmp<<' ';
print(l, tmp-1);
print(tmp+1, r);
}

int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i], f[i][i]=a[i];
for(int i=1;i<=n+1;i++) f[i][i-1]=1;
for(int i=n;i>=1;i--)
for(int j=i+1;j<=n;j++)
for(int k=i;k<=j;k++){
long long tmp=f[i][k-1]*f[k+1][j]+a[k];
if(tmp>f[i][j]){
g[i][j]=k;
f[i][j]=tmp;
}
}
cout<<f[1][n]<<endl;
print(1, n);
return 0;
}

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define go(i,a,b) for(int i = a ; i <= b ; i++)
#define long long LL
using namespace std;
const int maxn = 1000 + 5;
int n,ans,f[maxn][maxn],p[maxn][maxn],v[maxn];
void print(int l,int r)
{
int pos = f[l][r];
printf("%d ",pos);
if(l<=pos-1) print(l,pos-1);
if(r>=pos+1) print(pos+1,r); //输出遍历的位置
}
int dp(int l,int r)
{
if(l > r) return 1;
if(p[l][r] != -1) return p[l][r];
if(l == r) {
f[l][r] = l;
return v[l];
}int& ans = p[l][r] ; int& pos = f[l][r];
for(int i = l ; i <= r ; i++)

if(dp(l,i-1)*dp(i+1,r)+v[i]>ans)
{
ans=dp(l,i-1)*dp(i+1,r)+v[i];
pos=i;
}
return ans;
}
int main()
{
memset(p,-1,sizeof(p));
scanf("%d",&n);
go(i,1,n) scanf("%d",&v[i]);
cout<<dp(1,n)<<endl;
print(1,n);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];

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

int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
for (int len = 1; len < n; ++len) {
for (int i = 1; i + len <= n; ++i) {
int j = i + len;
f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空，如果有的话，这肯定不是最优解
root[i][j] = i;//默认从起点选根
for (int k = i + 1; k < j; ++k) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];

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

int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
for (int len = 1; len < n; ++len) {
for (int i = 1; i + len <= n; ++i) {
int j = i + len;
f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空，如果有的话，这肯定不是最优解
root[i][j] = i;//默认从起点选根
for (int k = i + 1; k < j; ++k) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}

dp练手题
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];

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

int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
for (int len = 1; len < n; ++len) {
for (int i = 1; i + len <= n; ++i) {
int j = i + len;
f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空，如果有的话，这肯定不是最优解
root[i][j] = i;//默认从起点选根
for (int k = i + 1; k < j; ++k) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}

区间dp，缘由是中序遍历中如果选定一个点为当前子树的根就可以以左右区分出左右子树，然后很明显这还是同一个问题，只是规模规模变小了。然后对子树继续这个操作直到边界条件我们就发现。。。就做完辣！
我还是用了记忆化搜索，写起来方便易懂。

debug小记
(30)开始，

    if (l == r) {
        cout << l << " ";
        return;
    }

不能忘，这表示的是叶子节点，因为之前写的时候并没有赋值给cut[x][x]，会定位到0，导致死循环。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXN = 100;

typedef long long ll;
ll n, val[MAXN], f[MAXN][MAXN], cut[MAXN][MAXN];

int dfs(int l, int r) {
    if (l > r) return 1;
    if (l == r) return val[l];
    if (f[l][r]) return f[l][r];
    for (int mid = l; mid <= r; mid++) {
        int res = dfs(l, mid - 1) * dfs(mid + 1, r) + val[mid];
        if (res > f[l][r]) {
            f[l][r] = res;
            cut[l][r] = mid;
        }
    }
    return f[l][r];
}

void recon(int l, int r) {  // tree reconstruction
    if (l > r) return;
    int mid = cut[l][r];
    if (l == r) {
        cout << l << " ";
        return;
    }
    cout << mid << " ";
    recon(l, mid - 1);
    recon(mid + 1, r);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    cout << dfs(1, n) << endl;
    recon(1, n);
    cout << endl;

    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];

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

int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
for (int len = 1; len < n; ++len) {
for (int i = 1; i + len <= n; ++i) {
int j = i + len;
f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空，如果有的话，这肯定不是最优解
root[i][j] = i;//默认从起点选根
for (int k = i + 1; k < j; ++k) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];

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

int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
for (int len = 1; len < n; ++len) {
for (int i = 1; i + len <= n; ++i) {
int j = i + len;
f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空，如果有的话，这肯定不是最优解
root[i][j] = i;//默认从起点选根
for (int k = i + 1; k < j; ++k) {
if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
root[i][j] = k;
}
}
}
}
cout << f[1][n] << endl;
print(1, n);
return 0;
}
```

令\(dp[l][r]\)为\([l,r)\)区间所构成的二叉树中权值最大的权值

则: \(dp[l][r] = \max_{m\in [l,r)} \{ dp[l][m]\cdot dp[m+1][r] + a[m] \}\)

对每次计算维护其最优分割\(m\)即可构造前序遍历。

import qualified Data.Map as M
import qualified Data.Array as A

maximize (x:[]) = (x,0)
maximize (x:xs)  =
    let (x1,i) = maximize xs
    in if x<x1 then (x1,i+1) else (x,0)

-- @param s 以前搜索过的状态的集合
-- @param m 对一个(Int,Int)构成区间的子树，其最高分值
-- @param p 对一个(Int,Int)构成区间的子树，其根
-- @param a 每个中序遍历到的节点的权值
-- @param x 需要查找的区间
-- @return 查找完成区间后新的搜索过的状态的集合
dp :: (M.Map (Int,Int) Int,M.Map (Int,Int) Int) -> 
    A.Array Int Int -> (Int,Int) -> 
    (M.Map (Int,Int) Int,M.Map (Int,Int) Int)
dp s@(m,p) a x@(l,r)
    | x `M.member` m = (m,p)
    | l == r     = (M.insert x 1 m,p)
    | l == r-1   = (M.insert x (a A.! l) m,M.insert x l p)
    | otherwise  = 
        let plst = [l..r-1]
            ss@(sm,sp) = foldl (\s d -> ensure (ensure s a (l,d)) a (d+1,r)) s plst
            (msm,par)  = maximize $
                map (\d -> sm M.! (l,d) * sm M.! (d+1,r) + a A.! d) plst
            ans@(ns,np)= (M.insert x msm sm,M.insert x (par+l) sp)
        in ans

predParse :: M.Map (Int,Int) Int -> (Int,Int) -> [Int]
predParse p x@(l,r)
    | l==r   = []
    | l==r-1 = [l]
    | otherwise =
        let d = p M.! x in
        [d] ++ predParse p (l,d) ++ predParse p (d+1,r)

main = do
    n <- readLn
    ln <- getLine
    let a = A.listArray(0,n-1) $ (map (read::String->Int).words) ln
    let (m,p) = dp (M.empty,M.empty) a (0,n)
    print (m M.! (0,n))
    let lst = map (+1) $ predParse p (0,n)
    putStrLn $ (unwords.map show) lst

这题应该搞个SPJ。。
一开始只要大于等于就更新，就WA，改成严格大于才更新就AC了

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

int n;
int a[31];
int root[31][31];
int f[31][31];
void print(int l,int r) {
    if (l>r) return;
    if (l==r) {
        cout<<l<<" ";
        return;
    }
    cout<<root[l][r]<<" ";
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    FOR(i,n) cin>>a[i];
    FOR(i,n) f[i][i]=a[i],root[i][i]=i;
    REP(len,2,n) {
        FOR(i,n) if (i+len-1<=n) {
            int j=i+len-1;
            REP(k,i,j) {
                int res;
                if (k==i) {
                    res=1*f[k+1][j]+a[k];
                } else if (k==j) {
                    res=f[i][k-1]*1+a[k];
                } else res=f[i][k-1]*f[k+1][j]+a[k];
                if (res>f[i][j]) {
                    f[i][j]=res;
                    root[i][j]=k;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    print(1,n);
    return 0;
}

#include<cstdio>
#include<cstring>
using namespace std;
int f[31][31],root[31][31];
int d[31];
void pre_dfs(int l,int r)
{
if(l<=r)
{
printf(" %d",root[l][r]);
pre_dfs( l , root[l][r]-1 );
pre_dfs( root[l][r]+1 , r );
}
}

int main()
{
int n;scanf("%d",&n);for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) f[i][j]=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&d[i]);
root[i][i]=i;
f[i][i]=d[i];
}
for(int k=2;k<=n;k++)
for(int L=1;L<=n-k+1;L++)
{
int R=L+k-1;
for(int mid=L;mid<=R;mid++)
{
if( f[L][R] < f[L][mid-1] * f[mid+1][R] + d[mid])
{
f[L][R]= f[L][mid-1]*f[mid+1][R]+d[mid];
root[L][R]=mid;
}
}
}
printf("%d\n",f[1][n]);printf("%d",root[1][n]);pre_dfs(1,root[1][n]-1);pre_dfs(root[1][n]+1,n);return 0;
}
//真的还好

import java.util.Scanner;

public class Main {
static Scanner in = new Scanner(System.in);
static int n;
static int[] a = new int[35];
static int[][] f = new int[35][35];
static int[][] root = new int[35][35];
public static void main(String[] args) {
n = in.nextInt();
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
f[i][j] = 1;
}
}
for (int i = 1; i <= n; i++) {
/**
* 直接赋给f[i][i],即叶子的加分就是叶节点本身的分数
* root[i][j]
* /
a[i] = in.nextInt();
f[i][i] = a[i];
root[i][i] = i;
}
/*
* f[i][j] 表示区间为i-j的最大加分时的根节点
* root[i][j] 表示区间在i-j内的父结点编号
* k 枚举区间长度 1--(n-1)
* i 枚举区间起点 1--(n-k)
* i+k 代表区间终点
* j 枚举区间中的根
* */
for(int k = 1; k < n; k++) {
for(int i =1 ; i + k <= n; i++) {
for(int j = i; j <= i + k; j++) {
int s = f[i][j-1] * f[j+1][i+k] + f[j][j];
if(s > f[i][i+k]) {
f[i][i+k] = s;
root[i][i+k] = j;
}
}
}
}

System.out.println(f[1][n]);
PT(1, n);
}
/**
* 输出
* */
private static void PT(int l, int r) {
if (l <= r) {
System.out.print(root[l][r] + " ");
PT(l, root[l][r] - 1);
PT(root[l][r] + 1, r);
}
}
}

一道树形（*区间*）DP

/*vijos1100 加分二叉树

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
By linus@chen
at CDFLS 2017.10.29 Sun
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 31
using namespace std;

inline int read()
{
char ch =getchar();int f=1,res=0;
while(ch>'9'||ch<'0'){ if(ch == '-') f=-1;ch = getchar();}
while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+ch - '0',ch = getchar();
return res*f;
}

int n,a[maxn],dp[maxn][maxn],path[maxn][maxn],p;//DP[i][j]记录i到j之间的节点的最大加分

inline int dfs(int l,int r)
{
if(dp[l][r]) return dp[l][r];
if(l > r) return 1;
if(l == r) dp[l][r] = a[l],path[l][r] = l;
else
{
for(int i=l;i<=r;i++)
{
int x = dfs(l,i-1) * dfs(i+1,r) + a[i];
if(x > dp[l][r])
dp[l][r] = x,path[l][r] = i;
}
}
return dp[l][r];
}

inline void front(int l,int r)
{
if(l>r) return;
printf( p ++ == 0 ? "%d" : " %d",path[l][r]);
front(l,path[l][r]-1);
front(path[l][r]+1,r);
}

inline void work()
{
n=read();
for(int i=1;i<=n;i++) a[i] = read();
dfs(1,n);
printf("%d\n",dp[1][n]);
front(1,n);
}

int main()
{
work();
return 0;
}

using namespace std;
const int N = 109; 
int ans[N][N]={0};int gen[N][N]={0};
inline void dfs(int l,int r)
{
    if ( l > r )    return ;
    if ( l == r )
    {
        printf("%d ",l);    return ;
    }
    printf("%d ",gen[l][r]);
    dfs(l,gen[l][r]-1);dfs(gen[l][r]+1,r);
}
int main()
{
    freopen("in.txt","r",stdin);
    int n; cin>>n; 
    
    for (int i = 0; i <= n+1; i++)
    for (int j = 0; j <= n+1; j++)
        ans[i][j]=1; 
        
    for (int i = 1; i <= n; i++)
        cin>>ans[i][i];
    
    for (int l = n; l >= 1; l--)
    for (int r = l+1; r <= n; r++)
    {
        int zgen=0;int maxgen=0;
        for (int k = l; k <= r; k++)
            if ( ans[l][k-1]*ans[k+1][r]+ans[k][k] > maxgen )
            {
                zgen = k;   maxgen=ans[l][k-1]*ans[k+1][r]+ans[k][k];
            }
        ans[l][r]=maxgen;
        gen[l][r]=zgen; 
    }
    
    printf("%d\n",ans[1][n]);
    dfs(1,n);
        
    return 0;