形式化题目

给定一个长度为 $n$ 的环形珠子序列，每颗珠子由二元组 $(head, tail)$ 构成。已知第 $i$ 颗珠子的尾标记等于第 $i+1$ 颗珠子的头标记（第 $n$ 颗珠子的尾标记等于第 $1$ 颗珠子的头标记）。 每次操作可选择相邻的两颗珠子 $(m, r)$ 和 $(r, n)$ 合并成一颗新珠子 $(m, n)$，同时释放能量 $m \times r \times n$。 共进行 $n - 1$ 次合并，直到只剩一颗珠子。求按某种次序合并所能释放的最大总能量。

正解

思路

本题是环形区间动态规划的经典问题，本质与矩阵链乘法模型完全相同。

1. 破环成链

项链构成一个环，但最终保留的珠子必定由环上某处断开后的一段链通过某种顺序合并而来。 处理环形区间问题的标准技巧是倍长序列： 将长度为 $n$ 的头标记序列 $a_0, a_1, \dots, a_{n-1}$ 复制一份拼接在末尾，形成长度为 $2n$ 的序列 $head$。 这样，环上所有长度为 $n$ 的珠子链，均与倍长序列中某个长度为 $n$ 的连续区间 $[i, i + n - 1]$（其中 $0 \le i < n$）一一对应。

区间 $[l, r]$（包含 $r - l + 1$ 颗珠子）合并后，生成的单个珠子的头标记恒为 $head[l]$，尾标记恒为 $head[r + 1]$。

2. 状态定义与转移

设 $dp[l][r]$ 表示将珠子区间 $[l, r]$ 完全合并成一颗珠子所能释放的最大总能量。

• 初始状态：单个珠子无法合并，不需要任何操作，$dp[i][i] = 0$。
• 状态转移：考虑区间 $[l, r]$ 的最后一次合并。设分割点为 $k$（$l \le k < r$），即左半部分 $[l, k]$ 合并成珠子 $(head[l], head[k+1])$，右半部分 $[k+1, r]$ 合并成珠子 $(head[k+1], head[r+1])$。最后一次合并两颗珠子释放的能量为 $head[l] \times head[k+1] \times head[r+1]$。 因此，状态转移方程为：

3. 计算顺序与答案

• 外层枚举区间长度 $len$ 从 $2$ 到 $n$；
• 内层枚举左端点 $l$（$0 \le l < 2n - len$），右端点 $r = l + len - 1$；
• 内部枚举分割点 $k$（$l \le k < r$）进行状态转移；
• 最终答案为所有长度为 $n$ 的区间的最大值：

样例推演

以输入 $n=4$，头标记为 [2, 3, 5, 10] 为例，倍长序列为 [2, 3, 5, 10, 2, 3, 5, 10]。 珠子编号 0~3 分别为 $(2,3), (3,5), (5,10), (10,2)$。

长度为 4 的最优区间起始于下标 3（即原珠子 3, 0, 1, 2），合并总能量达到最大值 $710$。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def max_energy(n: int, a: list[int]) -> int:
    """计算环形项链合并所能释放的最大总能量。

    破环成链：将长度为 n 的标记序列复制一份变为 2n。
    dp[l][r] 表示将区间珠子 [l, r] 完全合并成一颗珠子所释放的最大能量。
    合并后的新珠子头标记为 a[l]，尾标记为 a[r+1]。
    枚举最后一次合并的位置 k (l <= k < r)：
    左半部分合并成珠子 (a[l], a[k+1])，右半部分合并成珠子 (a[k+1], a[r+1])，
    最后合并释放 a[l] * a[k+1] * a[r+1]。
    """
    head = a + a
    dp = [[0] * (2 * n) for _ in range(2 * n)]

    for length in range(2, n + 1):
        for l in range(2 * n - length):
            r = l + length - 1
            dp[l][r] = max(
                dp[l][k] + dp[k + 1][r] + head[l] * head[k + 1] * head[r + 1]
                for k in range(l, r)
            )

    return max(dp[i][i + n - 1] for i in range(n))


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    print(max_energy(n, a))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:11
 * update_at: 2026-10-05 09:11
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 205; // 2n 最大为 200，留少量余量

ll n;
ll head[MAXN];     // 倍长后的头标记序列 head[1..2n]，满足 head[i+n] = head[i]
ll dp[MAXN][MAXN]; // dp[l][r] 表示把珠子区间 [l,r] 合并成一颗珠子释放的最大总能量

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> head[i];
    }
    // 破环成链：倍长序列后，环上任意连续 n 颗珠子都对应一个长度 n 的区间
    for (ll i = 1; i <= n; i++) {
        head[i + n] = head[i];
    }
}

void solve() {
    // 按区间长度从小到大递推，保证子区间先算好
    for (ll len = 2; len <= n; len++) {
        for (ll l = 1; l + len - 1 <= 2 * n - 1; l++) {
            ll r = l + len - 1;
            // 枚举最后一次合并的分割点 k：左半段 [l,k] 与右半段 [k+1,r] 先各自合并
            // 左半段合并后的珠子为 (head[l], head[k+1])，右半段为 (head[k+1], head[r+1])
            for (ll k = l; k < r; k++) {
                ll energy = dp[l][k] + dp[k + 1][r] + head[l] * head[k + 1] * head[r + 1];
                if (energy > dp[l][r]) {
                    dp[l][r] = energy;
                }
            }
        }
    }

    // 枚举环的断开位置，取所有长度为 n 的区间中的最大值
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        if (dp[i][i + n - 1] > ans) {
            ans = dp[i][i + n - 1];
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

• 时间复杂度：倍长后序列长度为 $2n$，区间长度从 $2$ 到 $n$，左右端点约 $2n$ 个，分割点 $k$ 枚举次数为 $len-1$ 次。总运算次数为 $\sum_{len=2}^n 2n(len-1) \approx n^2(n-1) = O(n^3)$。对于 $n \le 100$，$n^3 \approx 10^6$，在 1000ms 限时内可以在 0.05 秒内迅速完成。
• 空间复杂度：需要存储大小为 $2n \times 2n$ 的二维 DP 数组，空间复杂度为 $O(n^2)$，内存占用约几十 KB，远低于 128MB 限制。

总结

环形区间 DP 的核心是通过“倍长序列”打破环的对称性，将环上任意连续的 $n$ 颗珠子映射到线性序列中长度为 $n$ 的区间。 由于子区间合并后的珠子头尾标记仅由区间的左右端点决定，内部合并方式对外部完全透明，因而满足无后效性与最优子结构，可按区间长度从小到大进行递推求解。