加分二叉树

比较巧妙。其实还是自己的思维不行。我们不需要管这棵树是什么样子的，因为中序序列是1到n从小到大，且算分的条件表明选择不同的点为根就会有不同的结果，则我们要考虑哪个点作为根。定义dp[i][j]为i点到 j 点之间的点形成树的时候的最大值，并且用root[i][j]记录转移过程中选择的哪个点作为最优。

#include <bits/stdc++.h>using namespace std;#define ll long long
#define inf 0x3f3f3f3f
#define maxn 50
int dp[maxn][maxn];
int root[maxn][maxn];
int n;
void output(int l,int r)
{if(l>r) return ;printf("%d ",root[l][r]);if(l==r) return ;output(l,root[l][r]-1);output(root[l][r]+1,r);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&dp[i][i]),root[i][i]=i;for(int len=1;len<n;len++){    //枚举区间长度for(int i=1;i+len<=n;i++){    //枚举区间端点int j=i+len;dp[i][j]=dp[i+1][j]+dp[i][i];root[i][j]=i;    //左子树为空的情况if(dp[i][j]<dp[i][j-1]+dp[j][j]){    //考虑右子树为空的情况dp[i][j]=dp[i][j-1]+dp[j][j];root[i][j]=j;}for(int k=i+1;k<j;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];root[i][j]=k;}}}}printf("%d\n",dp[1][n]);output(1,n);return 0;
}