03年noip加分二叉树c语言程序
发布网友
发布时间：2024-09-29 05:23
共1个回答
热心网友
时间：2024-11-03 08:14
#include <stdio.h>
#include <string.h>
long n,t,l;
long a[50];
long b[50];
long gen[50][50]={{0},{0}};
long long f[50][50]={{0},{0}};
void init()
{
long i;
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld",&a[i]);
}
void DP()
{
long i,j,k;
for (i=0;i<=n;i++)
for (j=0;j<=n;j++)
{
if (i>j) f[i][j]=1;
if (i==j) f[i][j]=a[i];
}
for (i=n;i>=1;i--)
for (j=i;j<=n;j++)
for (k=i;k<=j;k++)
{
if (i==j)
{
gen[i][j]=i;
break;
}
if (f[i][j]<f[i][k-1]*f[k+1][j]+a[k])
{
gen[i][j]=k;
f[i][j]=f[i][k-1]*f[k+1][j]+a[k];
}
}
}
void digui(long left,long right)
{
long t1;
if (gen[left][right]!=0)
{
t++;
b[t]=gen[left][right];
t1=b[t];
digui(left,t1-1);
digui(t1+1,right);
}
}
void print()
{
long i;
printf("%I64d\n",f[1][n]);
digui(1,n);
t=0;
for (i=1;i<n;i++)
printf("%ld ",b[i]);
printf("%ld\n",b[n]);
}
int main()
{
init();
DP();
print();
return 0;
}追问求神犇大哥给我讲讲吧。。。
