$$\color{Red}{环形石子合并——》能量项链 详细题解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 N 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m×r×n（Mars单位），新产生的珠子的头标记为 m，尾标记为 n。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 N=4，4 颗珠子的头标记与尾标记依次为 (2，3)(3，5)(5，10)(10，2)

我们用记号 ⊕ 表示两颗珠子的聚合操作，(j⊕k) 表示第 j，k 两颗珠子聚合后所释放的能量。则

第 4、1 两颗珠子聚合后释放的能量为：(4⊕1)=10×2×3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。

输入格式
输入的第一行是一个正整数 N，表示项链上珠子的个数。

第二行是 N 个用空格隔开的正整数，所有的数均不超过 1000，第 i 个数为第 i颗珠子的头标记，当 i<N 时，第 i 颗珠子的尾标记应该等于第 i+1颗珠子的头标记，第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

输出只有一行，是一个正整数 E，为一个最优聚合顺序所释放的总能量。

数据范围

4≤ N ≤100 

1≤ E ≤2.1×109

输入样例：

4
2 3 5 10

输出样例：

710

1.算法细节

本题是也是环形区间DP，是环形石子合并的升级版

我的环形石子合并题解

而环形石子合并一个石子只有一个属性值即重量，而这道题一个能量石具有左值和右值，类似线性代数的思想，每个能量石的合并需要满足前一个能量石的右值等于后一个能量石的左值，并且合并后可以提供前一个能量石的左值乘它的右值（其实也等于右能量的左值）再乘右能量石的左值

从这个角度去看的话，我们一个石头需要两个值来代表它，因此我们的区间DP模板需要有很多修改

我们观察样例给我们的数据
例如：设 N=4，4 颗珠子的头标记与尾标记依次为 (2，3) (3，5) (5，10) (10，2)， 输入样例的序列是这个格式2 3 5 10，四个数显然只能看到三个区间，事实上还有一个区间(10, 2)用最后一个数字作为最后一个石子的左区间，而第一个数字作为它的右区间。

我们试着先从链形摆放的角度去思考怎么做这道题

为了能直接每两个数选择作为一个石子的区间，而避免最后一个石子的起点不满足一左一右相邻的格式，我们存储序列应该存储为2 3 5 10 2，这样从前到后每两个数字一组这么枚举，就能代表一个能量石，这里其实已经初见链形尾巴拼接自己等价为环的做法了

那么该如何思考区间DP的表示和转移问题 ？
那么从两个点的区间len代表一个石子的角度去考虑，如我们合成两个能量石，就和之前的合并石子大不相同，之前是一个点代表一个区间，且合并区间len=2合并两堆石子，这里假设合并 (3,5) (5, 10)，在我们存储石子结构中是这个数字序列：3 5 10，首先可以发现最起码len=3的时候才能合并，其次前一个石头的右值和后一个石头的左值用了相同的一个位置来表示。

从这两个角度考虑，按照闫式DP分析法，我们的状态方程应该这么表示：f[i][j]代表把第一个石子左值为i，最后一个石子的右值为j，这个区间内全部石子合并之后的集合，属性表示为MAX最大值

len=3的时候才能合并：故我们的len从2开始枚举（2是为了初始化初值，即单个能量石的能量大小，这道题为0），以前的石子合并我们的枚举的k满足条件为i <= k < j，因为区间为1的时候代表最小的单位，一个石子，所以可以划分区间为f[i][i]为一个石子，然后f[i][i+1]为最小的，两个石子合并。这道题应该是i < k < j，因为区间长度为2的时候才代表一个能量石头，所以k不能和i相等。

这里把 * 代表合成获取的能量
其次状态方程转移以前是f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + *)
这道题因为k这个划分点，同时包含前一个石头的右端点和后一个石头的左端点，这里可以直接用k划分
即：f[i][j] = max(f[i][j], f[i][k], f[k][j] + *);

那么这题的 * 能量怎么计算？

很简单，直接使用左区间的w[i]乘以划分点w[k]乘以右区间w[j]即可

• 那么如何把环转化为一个链呢？

其实我们可以这么想，把环形的石子看作一个个点，事实上应该是n + 1个点，每次选取其中的两个合并相当于给两堆连一条边，那么我们发现最后一定是连n条边，这样我们在区间dp的基础上，可以在外面嵌套一层大循环，枚举到底缺口在哪，只需要枚举n次，找到缺口即确定起点和终点

但这么做，相当于本身O(n ^ 3)的区间dp问题变成了O(n ^ 4)，这道题会超时

• 那么如何优化呢？

很简单，我们可以复制一份接到最开始的数组，变成两份，如 1 2 3 2 ——》 1 2 3 2 1 2 3 2
这样我们枚举区间长度还按n + 1来算，但是总石子多了n份，这样我们只需要从f[1][n+1] 枚举到f[n][n + n]寻找答案
复杂度变成了O((2n) ^ 3)

2.具体代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 210, n;
    static int[][] f = new int[N][N];
    static int[] w = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            w[i] = w[i + n] = Integer.parseInt(s1[i-1]);
        }
        for (int i = 1; i <= n << 1; i++) {
            //求最大值，初始化为负无穷,这道题其实不用，因为最小值就是0,不存在负数
            Arrays.fill(f[i], -0x3f3f3f3f);
        }
        for (int len = 2; len <= n + 1; len++) {
            for (int i = 1, j; (j = i + len - 1) <= n << 1; i++) {
                //初始状态初始化，即每个石子本身是没有能量的
                if (len == 2) f[i][j] = 0;
                for (int k = i + 1; k < j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]);
                }
            }
        }
        //枚举起点也就是环形先从哪个开始合成
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, f[i][i + n]);
        }
        System.out.println(res);
    }
}