分析
这是一道DP题,但是因为是个环,所以需要“破环为链”。
然后就是普通的区间DP了。根据套路,设$f[i] [j]$表示第i颗到第j颗珠子所能聚合的最大能量。
根据套路可得状态转移方程:
$f[i][j]=max{f[i][k]+f[k][j]+a[i]*a[k]*a[j]}$
不需要处理边界,但是要处理到$2n$。
答案即为$max\{f[i] [i+n]\}$。
代码
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int a[210];
int f[210][210];
int main()
{
int n; scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[n+i]=a[i]; //破环为链
}
for (int l=2;l<=n+1;l++) //区间长度
for (int i=1;i+l-1<=2*n;i++) //左界(要到2*n)
{
int j=i+l-1; //右界
for (int k=i+1;k<j;k++) //枚举中点
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]); //DP
}
int ans=-1;
for (int i=1;i<=n;i++) ans=max(ans,f[i][i+n]); //找最大值
printf("%d\n",ans); //输出
return 0;
}