python/TangDou/AcWing/Section/320.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 210;
const int INF = 0x3f3f3f3f;

int n;
int a[N];
int f[N][N];

int main() {
    scanf("%d", &n);
    // 破环成链
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i]; // 第 i 颗珠子的头标记

    // 区间DP模板
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n * 2; l++) { // 区间左端点
            int r = l + len - 1;                     // 区间右端点，r-l=l+len-1-l=len-1,举栗子：比如r=3,l=1,则len=3,len-1=3-1=2,符合事实
            for (int k = l; k < r; k++)              // 中间点k
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[l] * a[k + 1] * a[r + 1]);
            // 这里的过程同石子合并，这里不难想到若将l到k的珠子合并之后会变成一个首是l而尾k+1的珠子；
            // 同理若将k+1到r的珠子合并之后会变成一个首是k+1而尾r+1的珠子；
        }
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(f[i][i + n - 1], res); // 区间长度为n
    printf("%d\n", res);
    return 0;
}