AcWing 479. 加分二叉树
原题链接
中等
作者:
小卒无名
,
2021-02-12 14:05:22
,
所有人可见
,
阅读 308
#include <iostream>
using namespace std;
const int MAXN = 55;
int root[MAXN][MAXN];
void pre(int le,int ri)
{
if(le > ri) return ;
int k = root[le][ri];
printf("%d ",k);
pre(le,k-1);
pre(k+1,ri);
}
int a[MAXN][MAXN];
int main()
{
int n;
scanf("%d",&n);
int num[n+1];
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(int i=1;i<=n;i++)
{
for(int l = 1;l + i - 1 <= n;l++)
{
int rlen = i + l - 1;
for(int k = l;k <= rlen;k++)
{
int le = k==l?1 : a[l][k-1];
int ri = k==rlen?1 : a[k+1][rlen];
int sco = le*ri + num[k];
if(l == rlen) sco = num[k];
if(sco > a[l][rlen])
{
a[l][rlen] = sco;
root[l][rlen] = k;
}
}
}
}
cout<<a[1][n]<<endl;
pre(1,n);
return 0;
}