目录
题目大意
解题思路
这题用区间dp做，由于项链是环形的，可以先合并第一个和最后一个，所以要先做预处理，把项链复制一遍，使头尾相连。
f
i
,
j
f_i,_j
fi,j表示第
i
i
i个珠子到第
j
j
j个珠子合并所得的最大能量。枚举一个
k
k
k，表示先合并前
i
i
i到
k
−
1
k-1
k−1个，再合并后
k
k
k到
j
j
j个。由此可得状态转移方程为：
f
i
,
j
=
m
a
x
(
f
i
,
j
,
f
i
,
k
−
1
+
f
k
,
j
+
a
i
∗
a
k
∗
a
j
+
1
)
f_i,_j=max(f_i,_j,f_i,_{k-1}+f_k,_j+a_i*a_k*a_{j+1})
fi,j=max(fi,j,fi,k−1+fk,j+ai∗ak∗aj+1)
样例
输入
4
2 3 5 10
输出
710
代码
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
long long ans,f[1005][1005],a[1005];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}//输入加复制
a[n*2+1]=a[1];
n=n*2+1;
for(int i=1;i<n;i++) f[i][i]=0;
for(int d=1;d<=n;d++)//枚举后一段的长度
{
for(int i=1;i<=n-d;i++)//枚举第一段的长度
{
int j=i+d;//当前枚举的总长
for(int k=i+1;k<=j;k++)//枚举分割线
f[i][j]=max(f[i][j],f[i][k-1]+f[k][j]+a[i]*a[k]*a[j+1]);//转移，a[i]*a[k]*a[j+1]为合并所带来的能量
}
}
n=(n-1)/2;
for(int i=1;i<=n;i++)
{
ans=max(ans,f[i][i+n-1]);//寻找长度为n的最大值
}
cout<<ans;
return 0;
}