此题在校内oj上有一道，不过没有spj， 这份代码是能在洛谷上a，但是oj上没有

// 23/7/28/21:13
#include<bits/stdc++.h>
using namespace std;
long long a[45],dp[55][55],path[55][55],n;
void putt(int x,int l,int r){
    if(x){
        cout<<x<<' ';
        putt(path[l][x-1],l,x-1);
        putt(path[x+1][r],x+1,r);
    }
    
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];dp[i][i]=a[i];
        dp[i-1][i]=a[i-1]+dp[i][i];
        path[i][i]=i;path[i][i+1]=i;
    }dp[0][1]=0;//cin>>a[i];
    for(int i=n-2;i>=1;i--){
        for(int j=i+2;j<=n;j++){
            for(int k=i+1;k<j;k++){
                if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+dp[k][k]){
                    dp[i][j]=dp[i][k-1]*dp[k+1][j]+dp[k][k];
                    path[i][j]=k;
                   // node[k].l=k-1;node[k].r=k+1;node[k-1].in++;node[k+1].in++;
                }
                //cout<<dp[i][j]<<' ';
            }//cout<<endl;
        }
    }
    cout<<dp[1][n]<<endl;
    putt(path[1][n],1,n);
    return 0;
}

路径是wa的，并且有一组数据的最大值也是wa的 上面这份没有考虑边界，因为我认为边界取不到最大，另外长度也是从3开始的，因为2长度不需要讨论，所以提前存了。 下面这一份是都能a的代码，讨论了边界和2长度，但是我感觉这不会产生影响

// 23/7/28/21:13
#include<bits/stdc++.h>
using namespace std;
long long a[45],dp[55][55],path[55][55],n;
void putt(int l,int r){
    if(l<=r){
        cout<<path[l][r]<<' ';
        putt(l,path[l][r]-1);
        putt(path[l][r]+1,r);
    }
    return;
}
int main(){
    cin>>n;dp[n+1][n]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];dp[i][i]=a[i];
        dp[i][i-1]=1;
        path[i][i]=i;//path[i][i+1]=i+1;
    }//path[n][n+1]=0;//cin>>a[i];
    for(int i=n-1;i>=1;i--){
        for(int j=i+1;j<=n;j++){
            for(int k=i;k<=j;k++){
                if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+dp[k][k]){
                    dp[i][j]=dp[i][k-1]*dp[k+1][j]+dp[k][k];
                    path[i][j]=k;
                   // node[k].l=k-1;node[k].r=k+1;node[k-1].in++;node[k+1].in++;
                }
                //cout<<dp[i][j]<<' ';
            }//cout<<endl;
        }
    }
    cout<<dp[1][n]<<endl;
    putt(1,n);
    return 0;
}

想一早上了，求解