题目链接：https://loj.ac/problem/10151
解题思路
区间dp模板题，dp[i][j]表示区间[i,j]合并的最大价值，f[i][j]记录合并的位置，dp[i][j]=max(dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k])。每次在大于dp[i][j]的时候转移，并记录位置，最后bfs输出分离位置，第一次分离位置对应最后一次合并位置。
AC代码

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N=305;
struct node
{int l,r;
};
queue<node>q;
ll a[N];
ll sum[N];
ll dp[N][N];
int f[N][N];
int n;
void bfs(int x,int y)
{node tmp;tmp.l=x;tmp.r=y;q.push(tmp);while(!q.empty()){tmp=q.front();if(tmp.l==tmp.r){q.pop();continue;}printf("%d ",f[tmp.l][tmp.r]);int k=f[tmp.l][tmp.r];int rr=tmp.r;tmp.r=k;q.push(tmp);tmp.l=k+1;tmp.r=rr;q.push(tmp);q.pop();}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%lld",&a[i]);//sum[i]=a[i]+sum[i-1];}for(int len=2;len<=n;++len)for(int i=1;i<=n;++i){int j=i+len-1;if(j>n)break;for(int k=i;k<j;++k)if(dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k]>dp[i][j]){f[i][j]=k;dp[i][j]=dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k];//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;}}printf("%d\n",dp[1][n]);bfs(1,n);puts("");return 0;
}