能量项链(区间DP)

#include <iostream>
using namespace std;

// 因为不确定到底从哪个珠子开始，所以就开辟两倍大小空间，存储两次
const int N = 220;
int a[N];
int f[N][N];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i + n] = a[i];
    }

    // len = 3表示两个珠子，最后一个是和第一个相邻的，所以就可以在最后一个后边再放一个和第一个相同的，长度也就加1
    for (int len=3;len<=n+1;len++)
    {
        for (int i=1;i+len-1<=2*n;i++)
        {
            int j = i + len - 1;
            f[i][j] = -1e9;
            for (int k=i;k<j;k++)
                f[i][j] = max(f[i][j],f[i][k] + f[k][j] + a[i]*a[k]*a[j]);
        // 例如 1 2 3，因为中间的 2 是公用的，所以并不需要 k + 1
        // 首 1 尾 2，首 2 尾 3
        }
    }

    // 任意从某一个开始算起，找到最大能量
    int ans = -1e9;
    for (int i=1;i<=n;i++)
        ans = max(ans,f[i][i+n]);

    printf("%d\n",ans);
    return 0;

}