思路
- 首先想的是找一个根结点,而且是是分数最大的根节点
- 那么我们需要左右子树的最大分数.....循环下去
- 最终循环到一个点
- 其实我们需要左右子树的最大分数,就是一个区间的最大分数
- 可以转化为区间dp,从区间长度1开始更新(每次都要枚举根节点是谁)
- 时间复杂度 o(n^3)
参考代码
#include<iostream>
using namespace std;
const int N = 35;
int t[N];
int f[N][N];//f[i][j]表示从i-j的最大加分数
int n;
int root[N][N];
void dfs(int l,int r){
if(l>r)return;
int d = root[l][r];
cout<<d+1<<" ";
dfs(l,d-1);
dfs(d+1,r);
}
int main()
{
cin>>n;
for(int i=0;i<n;++i)cin>>t[i];
for(int len=1;len<=n;++len){
for(int i=0;i+len-1<n;++i){
int l=i,r=i+len-1;
for(int k=l;k<=r;++k){
int left = k==l?1:f[l][k-1];
int right = k==r?1:f[k+1][r];
int score = left*right+t[k];
if(l==r)score=t[k];
if(score>f[l][r]){
f[l][r]=score;
root[l][r]=k;
}
}
}
}
cout<<f[0][n-1]<<endl;
dfs(0,n-1);
return 0;
}