AcWing 479. 加分二叉树
原题链接
中等
作者:
wyf
,
2021-01-29 10:31:51
,
所有人可见
,
阅读 407
区间dp:分析题意我们可以得出我们需要枚举每一个节点,然后递归的算他的左子树最大值,右子树最大值,并将其相乘,最后加上该节点的值,(因为所有点的分数都为正,我们求乘积时才都取最大值,试想如果可以为负,那么是不是还应该多一种都取负数中最小值的情况,然后和两数都为正的情况取一个max),定义f[i][j]表示i~j中分数的最大值,g[i][j]用于记录取这个最大值时的根节点是多少,那么我们做的时候,只要score比f[i][j]大我们就更新f[i][j],同时记录此时的根节点g[i][j],最后f[1][n]即为答案,根节点则需要递归的求
#include<iostream>
using namespace std;
const int N=30;
int f[N][N],g[N][N],w[N];
void print(int l,int r){
if(l>r)return ;
int root=g[l][r];
cout<<root<<' ';
print(l,root-1);
print(root+1,r);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int len=1;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(len==1){
f[i][j]=w[i];
g[i][j]=i;
}
else{
for(int k=i;k<=j;k++){
int left=k==i?1:f[i][k-1];
int right=k==j?1:f[k+1][j];
int score=left*right+w[k];
if(score>f[i][j]){
f[i][j]=score;
g[i][j]=k;
}
}
}
}
cout<<f[1][n]<<endl;
print(1,n);
}