文字教学

这是一道环形区间动态规划问题，核心是将环形项链转化为线性数组，用区间DP记录最优解。

1. 破环为链：因为项链是环形的，我们把数组复制一份（长度变为2n），这样枚举长度为n的区间就能覆盖所有环形情况。
2. 状态定义：设 dp[i][j] 表示聚合第 i 到 j 颗珠子（线性化后）能获得的最大能量。
3. 状态转移：对于区间 i 到 j，枚举最后一步聚合的位置 k（i<=k<j），总能量为聚合 i~k 的能量 + 聚合 k+1~j 的能量 + 最后聚合这两部分的能量（a[i] * a[k+1] * a[j+1]）。
4. 初始状态：当 i==j 时，只有一颗珠子，能量为0。
5. 最终答案：所有长度为n的区间 dp[i][i+n-1] 中的最大值。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a[205];
ll dp[205][205];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len <= 2 * n; ++i) {
            int j = i + len - 1;
            dp[i][j] = 0;
            for (int k = i; k < j; ++k) {
                ll tmp = dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
                if (tmp > dp[i][j]) {
                    dp[i][j] = tmp;
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dp[i][i + n - 1]);
    }
    cout << ans << endl;
    return 0;
}