AcWing 479. 加分二叉树
原题链接
中等
作者:
1Accepted1
,
2021-01-29 20:44:59
,
所有人可见
,
阅读 273
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=35;
int f[maxn][maxn];
int root[maxn][maxn];
int w[maxn];
void print(int l,int r){
if(l>r) return ;
cout<<root[l][r]+1<<" ";
print(l,root[l][r]-1);
print(root[l][r]+1,r);
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;++i) cin>>w[i];
for(int len=1;len<=n;++len){
for(int l=0;l+len<=n;++l){
int r=l+len-1; //这一点一定要注意为什么要减一,因为当l==r时w值为该节点的分数,类似于先要初始化,。。。
for(int i=l;i<=r;++i){
int left=i==l?1:f[l][i-1];
int right=i==r?1:f[i+1][r];
int score=left*right+w[i];
if(l==r) score=w[i];
if(f[l][r]<score){
f[l][r]=score;
root[l][r]=i;
}
}
}
}
cout<<f[0][n-1]<<endl;
print(0,n-1);
cout<<endl;
return 0;
}