题解 | #能量项链#

题目链接

题目描述

在一个环形的项链上，有 $n$ 颗能量珠。每颗珠子 $i$ 有一个头标记 $h_i$ 和一个尾标记 $t_i$ 。相邻的两颗珠子 $B_i$ 和 $B_j$ （其中 $t_i = h_j$ ）可以合并，释放出 $h_i \cdot t_i \cdot t_j$ 的能量，并形成一颗头标记为 $h_i$ 、尾标记为 $t_j$ 的新珠子。要求找出一种合并顺序，将所有珠子合并为一颗，使得释放的总能量最大。

输入数据为 $n$ 个头标记，其中第 $i$ 颗珠子的尾标记等于第 $i+1$ 颗珠子的头标记（第 $n$ 颗的尾标记等于第 1 颗的头标记）。

解题思路

本题是区间动态规划（Interval DP）在环形结构上的一个典型应用，与经典的矩阵链乘问题非常相似。

1. 问题转化：处理环形结构

环形结构给 DP 带来了困难，因为没有固定的起点和终点。一个常见的处理技巧是“断环成链”：我们将原来的 $n$ 颗珠子序列复制一份接在后面，形成一个长度为 $2n$ 的链。这样，原来环上的任意连续 $n$ 颗珠子，都对应于这个长链上的一个长度为 $n$ 的子区间。

具体来说，如果输入的头标记序列是 $v_1, v_2, \dots, v_n$ ，我们构造一个新的标记数组 $a$ ，其中包含 $v_1, \dots, v_n, v_1, \dots, v_{n-1}$ 。这个新数组的长度为 $2n-1$ 。现在，问题就转化成了在这个链上求解所有长度为 $n$ 的区间的最大合并能量，再从这些结果中取最大值。

2. 状态定义

我们定义 $dp[i][j]$ 为将链上从第 $i$ 颗到第 $j$ 颗珠子合并成一颗所能释放的最大能量。我们的最终目标是 $\max_{i=1}^{n} \{dp[i][i+n-1]\}$ 。

珠子 $k$ 的头标记是 $a_k$ ，尾标记是 $a_{k+1}$ 。所以，合并珠子 $i$ 到 $j$ 这个区间，实际上是处理由标记点 $a_i, a_{i+1}, \dots, a_{j+1}$ 定义的珠子序列。

3. 状态转移

我们考虑区间 $[i, j]$ 的最后一次合并。这次合并必然是将一个已经合并好的子区间 $[i, k]$ 和另一个子区间 $[k+1, j]$ 合并而成的，其中 $i \le k < j$ 。

将区间 $[i, k]$ 的珠子合并，能得到的最大能量是 $dp[i][k]$ 。合并后的新珠子头标记为 $a_i$ ，尾标记为 $a_{k+1}$ 。
将区间 $[k+1, j]$ 的珠子合并，能得到的最大能量是 $dp[k+1][j]$ 。合并后的新珠子头标记为 $a_{k+1}$ ，尾标记为 $a_{j+1}$ 。
最后，将这两颗新珠子合并。根据能量释放规则，释放的能量为：第一颗珠子的头标记 $\cdot$ 第一颗珠子的尾标记 $\cdot$ 第二颗珠子的尾标记，即 $a_i \cdot a_{k+1} \cdot a_{j+1}$ 。

综合三部分，通过分割点 $k$ 得到的状态转移方程为： $dp[i][j] = \max_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + a_i \cdot a_{k+1} \cdot a_{j+1} \}$

4. 遍历顺序

与所有区间 DP 问题一样，我们按区间长度从小到大进行遍历。设区间长度为 $len$ ，从 2 遍历到 $n$ 。对于每个长度，我们再遍历区间的起始点 $i$ 。

$len$ 从 2 到 $n$ 。
$i$ 从 1 到 $2n - len$ 。
$j = i + len - 1$ 。
$k$ 从 $i$ 到 $j-1$ 。

最终，遍历所有可能的起点 $i$ （从 1 到 $n$ ），在 $dp[i][i+n-1]$ 中找到最大值即为答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    // 基础维度序列: v[0], v[1], ..., v[n-1], v[0]
    vector<int> dims = v;
    dims.push_back(v[0]);

    // 用于DP的链式维度序列, 1-based indexing
    vector<int> a(1, 0);
    a.insert(a.end(), dims.begin(), dims.end());
    // 追加 v[1]...v[n-1]
    a.insert(a.end(), dims.begin() + 1, dims.end() - 1);

    vector<vector<long long>> dp(a.size(), vector<long long>(a.size(), 0));

    for (int len = 2; len <= n; ++len) {
        // 链上有 2n-1 个珠子. 长度为 len 的链, 其起始位置 i 最大为 (2n-1) - len + 1 = 2n - len
        for (int i = 1; i <= 2 * n - len; ++i) {
            int j = i + len - 1;
            for (int k = i; k < j; ++k) {
                long long energy = (long long)a[i] * a[k + 1] * a[j + 1];
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + energy);
            }
        }
    }

    long long max_energy = 0;
    for (int i = 1; i <= n; ++i) {
        max_energy = max(max_energy, dp[i][i + n - 1]);
    }

    cout << max_energy << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }

        // 链式维度序列, 长度 2n, 采用 1-based indexing
        int[] a = new int[2 * n + 1];
        for(int i = 0; i < n; i++) {
            a[i+1] = v[i];
        }
        a[n+1] = v[0];
        for(int i = 1; i < n; i++) {
            a[n+1+i] = v[i];
        }
        
        long[][] dp = new long[2 * n + 1][2 * n + 1];

        for (int len = 2; len <= n; len++) {
            // 链上有 2n-1 个珠子. 长度为 len 的链, 其起始位置 i 最大为 (2n-1) - len + 1 = 2n - len
            for (int i = 1; i <= 2 * n - len; i++) {
                int j = i + len - 1;
                for (int k = i; k < j; k++) {
                    long energy = (long)a[i] * a[k + 1] * a[j + 1];
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][j] + energy);
                }
            }
        }

        long maxEnergy = 0;
        for (int i = 1; i <= n; i++) {
            maxEnergy = Math.max(maxEnergy, dp[i][i + n - 1]);
        }

        System.out.println(maxEnergy);
    }
}

n = int(input())
v = list(map(int, input().split()))

# 构造链式维度序列 a，采用 1-based indexing
# 序列由 v[0]...v[n-1], v[0], v[1]...v[n-1] 构成
# 总长度为 2n+1
a = [0] * (2 * n + 1)
for i in range(n):
    a[i + 1] = v[i]
a[n + 1] = v[0]
for i in range(1, n):
    a[n + 1 + i] = v[i]

dp = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]

# length 是区间内珠子的数量
for length in range(2, n + 1):
    # i 是区间的起始珠子编号
    # 链上有 2n-1 个珠子, 长度为 length 的链, 起始位置 i 最大为 (2n-1) - length + 1 = 2n - length
    for i in range(1, 2 * n - length + 1):
        j = i + length - 1
        # k 是分割点, 将珠子链 [i, j] 分为 [i, k] 和 [k+1, j]
        for k in range(i, j):
            energy = a[i] * a[k + 1] * a[j + 1]
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + energy)

max_energy = 0
# 结果是所有长度为 n 的链中的最大值
for i in range(1, n + 1):
    max_energy = max(max_energy, dp[i][i + n - 1])

print(max_energy)

算法及复杂度

算法：区间动态规划 (Interval Dynamic Programming)，通过复制数组将环形问题转化为链式问题。
时间复杂度： $\mathcal{O}(n^3)$ 。处理加倍后的链需要三层循环：枚举区间长度 $len$ （ $\mathcal{O}(n)$ ），枚举起始点 $i$ （ $\mathcal{O}(n)$ ），枚举分割点 $k$ （ $\mathcal{O}(n)$ ）。
空间复杂度： $\mathcal{O}(n^2)$ 。我们需要一个二维数组 $dp$ 来存储状态，其大小与 $2n \cdot 2n$ 成正比。