比赛 |
2025暑期集训第4场 |
评测结果 |
AAAAAAA |
题目名称 |
加分二叉树 |
最终得分 |
100 |
用户昵称 |
rb_tree |
运行时间 |
0.018 s |
代码语言 |
C++ |
内存使用 |
3.67 MiB |
提交时间 |
2025-07-05 09:05:21 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*w;
}
void write(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x>=10) write(x/10);
putchar((x%10)^48);
}
int n,dp[35][35],rt[35][35];
void dfs(int x,int l,int r)
{
write(x);
putchar(' ');
if(l==r) return;
int lr=rt[l][x-1],rr=rt[x+1][r];
if(lr>=1&&lr<=n) dfs(lr,l,x-1);
if(rr>=1&&rr<=n) dfs(rr,x+1,r);
}
signed main()
{
freopen("jfecs.in","r",stdin);
freopen("jfecs.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++) dp[i][j]=1;
}
for(int i=1;i<=n;i++) dp[i][i]=read();
for(int d=1;d<=n;d++)
{
for(int i=1;i<=n-d+1;i++)
{
int j=i+d-1;
dp[i][j]=dp[i+1][j]+dp[i][i];
rt[i][j]=i;
for(int k=i+1;k<=j-1;k++)
{
if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+dp[k][k])
{
dp[i][j]=dp[i][k-1]*dp[k+1][j]+dp[k][k];
rt[i][j]=k;
}
}
}
}
write(dp[1][n]);
putchar('\n');
dfs(rt[1][n],1,n);
fclose(stdin);
fclose(stdout);
return 0;
}