洛谷P1040 加分二叉树题解

dp即可

\(f[i][j]\)表示i到j的加分

相当于区间dp了

#include<cstdio> using namespace std; int v[50]; int f[55][55]; int root[55][55]; void print(int l,int r) { if(l>r)return ; if(l==r) { printf("%d ",r); return ; } int tmp=root[l][r]; printf("%d ",tmp); print(l,tmp-1); print(tmp+1,r); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); f[i][i]=v[i]; f[i][i-1]=1; } for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { for(int k=i;k<=j;k++) { if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k]))//k为根节点 { f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k]; root[i][j]=k; } } } } printf("%d\n",f[1][n]); print(1,n);//输出中序遍历 return 0; }