题解（A88.加分二叉树）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[50],dp[50][50],root[50][50];
void print(int l,int r){
if(l>r)return;
int rt=root[l][r];
cout<<rt<<' ';
print(l,rt-1);
print(rt+1,r);
}

int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i][i]=a[i];
root[i][i]=i;

}

for(int l=1;l<n;l++){
    for(int i=1;i+l<=n;i++){
        int j=i+l;

        if(dp[i+1][j]+a[i]>=dp[i][j-1]+a[j]){
            dp[i][j]=dp[i+1][j]+a[i];
            root[i][j]=i;
        }
        else{
            dp[i][j]=dp[i][j-1]+a[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]+a[k]){
                dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
                root[i][j]=k;
            }
        }
    }
}



/*for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        cout<<dp[i][j]<<' ';
    }
    cout<<endl;
}*/


cout<<dp[1][n]<<endl;
print(1,n);
return 0;
}