明显的动态规划题目

状态：
f[i][j] 段[i,j]所能得到的最大分数

转移：
max(f[i][k-1]*f[k+1][j]+v[k]) i<=k<=j

解
f[1][n]

时间
O(n^3)

空间
O(n^2)

/*
 加分二叉树
 Program by Alex
 13-08-07 09:43
*/

#include <stdio.h>

#define maxn 30+1

int d[maxn][maxn],root[maxn][maxn];

int v[maxn];

int n;

int f(int a,int b,int c){
 if(d[a][b]) return d[a][b];
 if(b<a) return 1;
 if(a==b){
 root[a][b]=a;
 return v[a];
 }
 int i,now,best=0,tl,tr;
 for(i=a;i<=b;i++){
 now=f(a,i-1,c+1)*f(i+1,b,c+1)+v[i];
 if(now>best){
 best=now;
 root[a][b]=i;
 }
 }
 d[a][b]=best;
 return best;
}

void display(int a,int b){
 printf("%d ",root[a][b]);
 if(a<root[a][b]) display(a,root[a][b]-1);
 if(b>root[a][b]) display(root[a][b]+1,b);
}

int main(){
 freopen("vijos1100.in","r",stdin);
 freopen("vijos1100.out","w",stdout);
 scanf("%d",&n);
 int i;
 for(i=1;i<=n;i++)
 scanf("%d",&v[i]);
 printf("%d\n",f(1,n,1));
 i=1;
 display(1,n);
 return 0;
}

大哥你做错了OK？
#include<iostream>
#include<cstring>
using namespace std;
//int max_nodes=40;
int n;
long best[40][40];
int root[40][40];
bool first;
void visit(int i,int j)//当前序遍历为1，2，3，4，5。。。时，中序遍历的求法。 
{
     if(i>j)
       return ;
     if(first)
      first=false;
     else 
       cout<<" ";
     cout<<root[i][j];
     visit(i,root[i][j]-1);
     visit(root[i][j]+1,j);
         
} 
long Search_Best(int l,int r)
{
      int i;
      long now;
      if(l>r) return 1;
      else
       {
           if(best[l][r]==-1)
             {
                 for(i=l;i<=r;i++)
                   {
                       now=Search_Best(l,i-1)*Search_Best(i+1,r)+best[i][i];
                       if(now>best[l][r])
                        {
                            best[l][r]=now;
                            root[l][r]=i;
                        }    
                   }    
             }    
        return best[l][r];
       }    
}    
int main()
{
        
     freopen("binary.in5","r",stdin);
     freopen("out3.txt","w",stdout); 
    while( cin>>n)
    {
     memset(best,-1,sizeof(best));
     memset(root,-1,sizeof(root));
     for(int i=1;i<=n;i++)
       { cin>>best[i][i];
          root[i][i]=i;
        }
     cout<<Search_Best(1,n)<<endl;
     first=true;
     visit(1,n);
     cout<<endl<<endl;    
    }      
     return 0;
}