NOIP2003 加分二叉树的问题

题目描述

   设一个n个节点的 二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为 di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下:

subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；

（1）tree的最高加分

（2）tree的前序遍历

输入描述

第1行：一个整数n（n<30），为节点个数。

第2行：n个用空格隔开的整数，为每个节点的分数（分数<100）。

输出描述

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。

第2行：n个用空格隔开的整数，为该树的前序遍历。

样例输入

5
5 7 1 2 10

样例输出

145
3 1 2 4 5我的代码思路：f[i][j]表示的是从第i个节点开始，共j个节点组成的树的最优值，然后初始化，接着f[i][j]=max(l*r+d[i+k-1]) l表示左子树的f值，r表示右子树的f值（枚举k=1~j），据说思路没错，但是程序就是弄不出正确答案，我也试过手动填表，结果和电脑的都不一样，能不能帮我看看，错哪里了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF sizeof(long)
int max(int a,int b)
{
    return (a>b? a:b);
}
int n;
int d[35];
long f[35][35];
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    int i,j,k;
    for(i=1;i<=n;i++) scanf("%d",&d[i]);
    for(j=1;j<=n;j++)
    for(i=1;i+j-1<=n;i++)
    {
    if(j==1) f[i][j]=d[i];
    else
    for(k=1;k<=j;k++)
         {
         f[i][j]=-INF;
         int l,r;
         if(k==1) l=1;
         else l=f[i][k-1];
         if(k==j) r=1;
         else r=f[i+k][j-k];
         f[i][j]=max(f[i][j],l*r+d[i+k-1]);
         }
    }
    printf("%d\n",f[1][n]);
    for(i=0;i<=n;i++)
    for(j=0;j<=n;j++){
    //printf("%5d",f[i][j]);
if(j==n)printf("\n");
}
    return 0;
}

•设f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分，则有：
f(i,j)=max{f[i,k-1]*f[k+1,j] +d[k]}
•显然 f(i,i)=d[i]
•答案为f(1,n)
•1<=i<=k=<=j<=n
•时间复杂度  O(n3)
•要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为i,i+1,…,j的二叉树的取最优决策时的根结点为k
•最后前序遍历这个树即可。
#include <stdio.h>
#define MAXN 29
#define MAXN1 30
typedef int int_arr[30];
unsigned long m1[MAXN1][MAXN1];
int_arr d,work;
int_arr m2[MAXN1][MAXN1];
main()
{
  int i,j,k,n,ji,r;
  unsigned long p,t;
  FILE *fp;
//输入
  if ((fp=fopen("tree.in","r"))==NULL) return(0);
  fscanf(fp,"%d",&n);
  for(i=1;i<=n;i++)
   {fscanf(fp,"%d",&d[i]);
    m1[1][i]=d[i];
    m2[1][i][1]=i;
   }
  fclose(fp);
 for(i=1;i<=n-1;i++)
   {
    m1[2][i]=d[i]+d[i+1];
    m2[2][i][1]=i; m2[2][i][2]=i+1;
   }
 for (i=3;i<=n;i++)
   for(j=1;j<=n+1-i;j++)
    {ji=j+i-1;
    t=0;
    for(k=j;k<=ji;k++)
    { if(k==j)
    p=m1[i-1][j+1]+d[j];
    else if(k==ji)
    p=m1[i-1][j]+d[ji];
    else
    p=m1[k-j][j]*m1[i-(k-j)-1][k+1]+d[k];
    if(p>t)
    {t=p; work[1]=k;
    for(r=2;r<=k-j+1;r++)
    work[r]=m2[k-j][j][r-1];
    for(r=k-j+2;r<=i;r++)
    work[r]=m2[i-(k-j)-1][k+1][r-(k-j+1)];
    }
    }
    m1[i][j]=t;
    for(r=1;r<=i;r++)
    m2[i][j][r]=work[r];
    }
 //输出
 if ((fp=fopen("tree.out","w"))==NULL) return(0);
 fprintf(fp,"%lu\n",m1[n][1]);
 for(i=1;i<=n;i++)
  fprintf(fp,"%3d",m2[n][1][i]);
 fprintf(fp,"\n");
 fclose(fp);
 
}