算法分析

此题是环形合并石子的升级版，细节比较多

按照环形合并石子的方式，将环形拆分成链形

• 状态表示：f[L][R]表示将所有[L,R]合并成一个珠子的所消耗能量的最大值

• 状态计算：

  将f[L,R]的左边划分到k，其中L + 1 <= k < R，其子集有如下情况：

  • f[L,L + 1]的集合，最大能量值为f[L,L + 1] + f[L + 1,R] + w[L] * w[L + 1] * w[R]

  • f[L,L + 2]的集合，最少次数为f[L,L + 2] + f[L + 2,R] + w[L] * w[L + 1] * w[R]

  • …

  • f[L,k]的集合，最少次数为f[L][k] + f[k][R] + w[L] * w[k] * w[R]

注意：这里 len 需要枚举到 n + 1，例如有4个数，2 3 5 10，可以合成能量的连续区间是(2，3) (3，5) (5，10) (10，2)，分别对应着 2 3 5 10 2 共5个数的位置，因此长度必须取到n + 1

时间复杂度 $O(8n^3)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 210;
    static int n;
    static int[] w = new int[N];
    static int[] s = new int[N];
    static int[][] f = new int[N][N];
    static int INF = 0x3f3f3f3f;
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1;i <= n;i++)
        {
            int x = scan.nextInt();
            w[i] = x;
            w[i + n] = x;   
        }

        for(int len = 3;len <= n + 1;len ++)
        {
            for(int L = 1;L + len - 1 <= n * 2;L ++)
            {
                int R = L + len - 1;
                f[L][R] = -INF;
                for(int k = L + 1;k < R;k ++)
                {
                    f[L][R] = Math.max(f[L][R], f[L][k] + f[k][R] + w[L] * w[k] * w[R]); 
                }
            }
        }
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            res = Math.max(res, f[i][i + n]);
        }
        System.out.println(res);
    }
}